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.

## An Example

(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.

1. 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
1. 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...

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

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

1. 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.