Why higher order procedures??

Question

So if a language provides higher order procedure then I can have procedure that returns procedure... something like

(define (Proc a b c) (lambda (x) ( // method body here in terms of a b c and x)))

To create new proc I would just do something like..

(define ProcA (Proc a1 b1 c1)) // Would create ProcA that has 1 argument

Similar task could be done in a language which does not support higher order procedure by defining Proc that takes 4 instead of 3 arguments and calling this procedure to define ProcA.. like

(define (Proc a b c x) ( // method body -- does not return any procedure)

(define (ProcA x) (Proc a1 b1 c1 x))

So why is there so much fuzz about higher order procedure.. Am I missing something..

Answer 1

This is more about mindset than feasibility. It allows you to treat functions as first-class citizens and think in terms of functions that operate on functions to create other functions, etc.

Obviously you could do or simulate this with other languages, but if it's not a syntactic mechanism it's kind of treated as an addition or a hack.

Answer 2

OK, but in the second example, you're creating that procedure at compile time with a pre-ordained list of a1, b1, and c1. In the first example, you're creating it at runtime when you call ProcA, and you can create as many different ones as you please, so you can do much more interesting things.

Answer 3

Think of a transform function or a sorting algorithm through an array. Now, you want to make it really flexible as to let the user of your function to specify the behaviour of your function by letting them pass a function as an argument.

Say, you write a sorting algorithm with the following procedural prototype:

sort(Array a, void (*fn)(a::element_type, a::element_type));

The user of that function could specify, by passing the appropriate fn, if they want a descending or ascending ordering.

Answer 4

I won't try to recapitulate the argument here, but in Why Functional Programming Matters, John Hughes argues that higher-order functions are useful because they provide more effective ways to "glue together" parts of a program, and thereby they make it easier to reuse code. The examples are in a very old language that is no longer used much, but they are still easy to follow and pretty convincing. Reading John's paper is a good way to get a detailed answer to your question "why is there so much fuzz about higher-order procedures".

Answer 5

It's a good observation that a function that returns another function is the same as a function that takes two arguments. This is called "Currying". Put another way, a function from A to B is proof of a logical implication, that A implies B, or:

A => B.

As you note, if A implies that B implies C, then A and B implies C, or:

(A => (B => C)) <==> ((A, B) => C)

But a higher order function is not necessarily a function that returns another function. A higher-order function is a function that takes another function as its argument. This is an important difference, and HOFs are immensely powerful programming tools.

For example, consider this Haskell function:

map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : (map f xs)

This higher-order function takes a function f and applies it to every element in a list. In languages without HOFs, you would do what this function does with a loop or something similar, but in a language that has HOFs, you can call f for every element in the list with a simple call like this:

map f myList

Sure, control constructs in languages let you approximate higher-order functions, but a language that has higher-order functions lets you invent your own control constructs. Scheme certainly qualifies.

Answer 6

You would need an inner-class to properly simulate that. The first case, Proc is closed over a, b and c. In the second case, the caller of ProcA cannot control how a1, b1 and c1 are passed to the other procedure, he can only control x. So, the way you control a1, b1 and c1 are through the use variables at a higher scope (module level or some such), which makes your function not pure. In that case, you cannot ensure that given the same arguments across calls, ProcA will return the same result. Where as with Proc, you can always be sure that if you call it with the same arguments, the same results will happen.

Answer 7

I use higher-order functions in javascript, for example, when I use a select box. I can pass in the function that will be called when an option is selected, as the only difference for me was that, which simplifies my code, it reduces redundancy.

I see the same thing in other languages I use that supports higher-order functions, as I can then start to look at how to clean up my code, where there is some redundancy that can be localized, and any differences can be done in a function.

Once C# supported this, I knew it was now more mainstream. :)