Here's a old usenet post on higher order functions I authored which does a nice job explaining why you'd want to do such a thing. I had posted it to comp.lang.ml. Some people had disagreed with my inclusion of the C++ link which implemented higher order functions in C++ because in some ways it was a restricted implementation. I leave it in with the comment that all things are possible, but not necessarily fun to use. :)

-pete

From: Peter Keller (psilord@data.upl.cs.wisc.edu)
Subject: Re: Any one understand higher order functions?
View: Complete Thread (89 articles)
Original Format
Newsgroups: comp.lang.ml
Date: 2002-10-01 07:25:31 PST

Thaddeus L Olczyk wrote:
: Someone just advocated the advantages of using higher order functions.
: I'm relatively new to FP but do want to see if it works. So I asked
: for examples. What I got instead were slogans and one really lame
: example which shows nothing.

Hello,

Now, I'm a scheme programmer, and I'm going to post scheme here. I'm sorry and I know it should be in ML. But I'm answering his general question about why are higher order functions are useful and will keep the scheme to a minimum since I don't know enough ML yet to do justice with my answer, though I submit my code is easily and readily translatable into ML.

Concerning higher-order functions:

The trivial examples that don't really explain why it is useful.

> (map (lambda (x) (* x x)) '(1 2 3 4 5 6 7))
(1 4 9 16 25 36 49)
> (filter even? '(1 2 3 4 5 6 7 8))
(2 4 6 8)

Yeah, yeah, you can implement this stuff with your eyes closed, we all know that--which is why it wasn't useful. It doesn't show the realization of why it is important.

How about something more meaningful, which ultimately is what programming is about--manipulating meaningful things in meaningful ways.

Imagine an employee database and some operations you'd like to perform on it.

Suppose you need to fire people who are late after so many days:
In pseudo code:
function (fire-if-late-more-days-than x database) :
for each employee in the database
    if (late-more-days-than 3 employee)
        yes: (you-are-fired employee)
        no: continue

So, using higher order functions, you can use map and filter to get the same effect like this:

(map you-are-fired (filter (late-days-or-more 3) employee-dataset))

(late-days-or-more 3)--actually another higher-order function, returns a function which takes a single employee record and returns true or false, if filter sees true, then it keeps the employee record in the list it is accumulating.

you-are-fired is a function that accepts an employee record and mails them they are fired and removes their login accounts and returns true if successful.

Now, map and filter, being higher order functions, allow more expression in the things you can do. Suppose you have some more action and selection functions:

(map send-cookies (filter (not-missed-work-more-days-then 1825) employees)
(map send-paycheck (filter all employees)) ;; all constantly returns true....

So, instead of writing two more first order functions(what I wrote in pseudo code) to represent the above two map calls(and writing more and more of them for each idea you want to represent), you can use higher-order functions to "do the selection loop" on the data thus abstracting the looping and application of the action mechanism.

Now, you can go even further with higher-order functions:
(define decision
    (lambda (action selection db)
    (map action (filter selection db))))

Now, you've abstracted away HOW the action is being performed on the selected employees in the database.

Now the concept to express your actions will more follow the actual reasoning patterns behind what you want to do in this specific problem domain.
(decision you-are-fired (late-days-or-more 3) employees)
(decision send-cookies (not-missed-work-more-days-then 1825) employees)
(decision send-paycheck all employees)

In effect, I've implemented a semantic language for decisions about employees. HOW all of this stuff gets done is now abstracted by 'decision', and if I need to change the underlying APIs or control structures(suppose I made the map parallel so it executes all actions simultaneously on a 1000 node cluster) I don't have to change the decision API at all since all it knows about are action and selection functions (and the database binding).

If you have lots and lots of selection and action functions(easily imagined), you can easily see where the improvement in readability and describability of the system appears.

The essence of higher-order functions is to abstract away control structures and since they can have state as well(called a closure), they can model objects. The reason this is nice is because the *same idea* (higher-order functions) can be used to express many different types of commonly used control patterns in addition to object modeling(which is just a special case of control abstraction anyway). You can't really use the syntactic sugar argument even though it *is*(AFAIK) true you can get by with no higher order functions at all. However, that would be like doing long division in Roman numerals. Yeah, it is possible, but the syntactic sugar of the decimal number system makes it ten times faster to perform the work. And ultimately, since it is a human writing these codes, being able to manipulate operations on data or sets of functions _in a way understandable by someone else_ gives the advantage to using higher order functions.

Of course, you can do higher order functions on other languages and implement near identical things to what I've just done and here's an example of such a thing:
http://okmij.org/ftp/c++-digest/Lambda-CPP-more.html

The important thing though, is WHY you'd want to do it, not that one language really express it better than another. Though, to bring up the Roman numeral analogy again, use a language's common path(meaning easily remembered and being the "shtick" of the language) strengths. FP languages tend to represent higher-order functions way easier than imperative languages.

One(that I can think of) drawback to higher-order functions is that if you use oddly constructed higher-order function algorithms, it can be really hard to figure out what is going on, but hey, that's true of C++'s object hierarchies, or frankly, any other language's abstraction mechanisms. It is only the discipline of the programmer that separates the "good" code from the "bad" code--and that will never change.

Sorry for posting scheme in an ML newsgroup, and I hope I answered this guy's question. Your mileage may vary.

-pete