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.