Higher-order functions are functions that take other functions as parameters, create functions or return functions.

The use of higher-order functions with PolymorphicTypes results in a style of programming that rivals ObjectOrientation for expressiveness. Some may assert it beats it.

ML, Haskell, LISP, Python all allow full use of high-order functions. C allows you to pass functions as arguments, but their usefulness is rather limited.

(This follows on from the the example in PolymorphicTypes.)

Glyn want make new trees from old ones by changing the leaves. So he writes a function to do this for him. One of its parameters will be a function that takes the value of a leaf and returns the changed value.

**let rec**map change tree =**match**t**with**| Leaf value -> Leaf (change value) | Node (left, right) -> Node (map change left, map change right) ;;

val map : ('a -> 'b) -> 'a tree -> 'b tree = <fun>

Once again Ocaml has worked out the types for itself. (**a -> b -> c** is ML for "function that takes parameters of the types **a** and **b** and returns a value of type **c**.) It's also noted that if the **change** function doesn't return the same type as its given then the **map** function will return a tree of a different type. Good. That's what Glyn wanted. (If it wasn't he could add some type annotations to say so.)

- Here's a function that can be used as a
**change**parameter - string_of_int ;;

*- : int -> string = <fun>*

You can guess what that does. **map**'s type is **('a -> 'b) -> 'a tree -> 'b tree**, so if I give it **string_of_int** as its first parameter then **'a** will be **string** and **'b** will be **int**, so **map** should return a **string tree**...

**let**numtree = Node (Node (Leaf 1, Leaf 2), Leaf 3) ;;

val numtree : int tree = Node (Node (Leaf 1, Leaf 2), Leaf 3)

- map string_of_int numtree ;;

- : string tree = Node (Node (Leaf "1", Leaf "2"), Leaf "3")

And it does!

If he writes a few more functions like this he will have a reusable library of binary tree operations. ML makes writing reusable code and easy and *reliable* process.

There's a lot more things you can do with higher-order functions, some of them very painful. What I've shown you there's at least *one* good thing you can do with them.

2 pages link to HigherOrderFunctions: