Why higher order procedures?

问题:

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 procedure, 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?

回答1:

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.

回答2:

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

回答3:

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.

回答4:

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.

回答5:

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.

回答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.

回答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. :)

回答8:

If a function accepts and/or returns a function, it is called a higher-order function (HOF). For inexperienced programmers, coming from C, C++, or Java, higher-order functions sound like magic, but they are very simple. Imagine a simple function that returns the result of 2 + 3:

(define (foo) (+ 2 3)) ;; (foo) => 5

That's a boring function, it always adds 2 to 3. What if we generalize it, so that it adds 2 not only to 3, but to any user-provided number?

(define (foo n) (+ 2 n)) ;; (foo 10) => 12

When a language doesn't support higher-order functions, you are forced to think that functions and values (e.g. numbers, booleans, lists) are 2 distinct things. But functional programming (FP) blurs distinction between them. Imagine that the only difference between a function and a value is that a function can be called, other than that you can do to a function whatever you could to a 2 or #t or '(a b c): you could give it as an argument, or return from a function, or store in a variable, or put it in a list. For example, let's generalize our little function further, so not only it could add 2 to n, but multiply 2 by n, or apply any other function that would accept two numbers:

(define (foo f n) (f 2 n))
;; (foo + 10) => 12
;; (foo * 10) => 20
;; (foo expt 10) => 1024

When you realize that a function can be treated the same way a number or a string is treated, anonymous functions (called “lambdas” in FP jargon) make complete sense. Anonymous functions are actually more basic and “normal” than ordinary named functions, named functions are just anonymous functions put into a variable, just like we put a number into a variable to use it multiple times.

(+ 2 2) ;; is no different from:
(let ((a 2)) (+ a a))
(lambda (x y) (* x y)) ;; is no different from:
(define (foo x y) (* x y)) ;; which is an abbreviation for:
(define foo (lambda (x y) (* x y))).

So HOFs allow us to generalize our functions to make them super-flexible. If you look at your function, see the logic behind it, you can realize, that if something operates on your data, then something else could probably too. If you add 2 numbers together, you could probably multiply them, or subtract, or exponentiate one to another, or whatever. Instead of writing a new function for every case each time, you could just accept an additional parameter, which has to be a function.

In FP we use HOFs all the time, for example, when manipulating lists. 3 functions are bread and butter of FP: map, filter and foldl. map accepts a function with 1 argument, applies this function to every element of a list, and returns a new list with changed elements. filter accepts a predicate (function that returns a boolean) with 1 argument, applies the predicate to every element of a list, and returns a new list with elements that do not satisfy the predicate removed.

(map (lambda (n) (+ n 1)) '(1 2 3 4 5) ;; '(2 3 4 5 6)
(define (foo n) (+ n 1))
(map foo '(1 2 3 4 5)) ;; '(2 3 4 5 6)
(filter (lambda (n) (> n 3)) '(1 2 3 4 5)) ;; '(4 5)
(define (bar n) (> n 3))
(filter bar '(1 2 3 4 5)) ;; '(4 5)

Imagine, you have a list of 1-arity functions—again, you can do whatever you want with a function, and store it in a data structure too—and you want to apply all of them to the same number, and get a list of results.

(let ((xs (list (lambda (x) (+ x 1))
                (lambda (x) (* x 2))
                (lambda (x) (- x)))))
  (map (lambda (f) (f 10)) xs)) ;; => (11 20 -10)

Conclusion: when a programming language properly supports functional programming concepts, higher-order functions allow flexibility and generality, which makes your code both more powerful (you can use the same function for various use-cases) and concise (no need to write 10 versions of one function). Some higher-order functions are used heavily in functional programming, so you get rid of low-level and verbose for-loops and write one-liners that do everything instead.

Note: foldl, which is the same as “left fold” or “left reduce”, is even more powerful. If you're really interested and have time, please read the first half of my answer using reduce. While it isn't written for Scheme/Racket, but instead for Common Lisp/Emacs Lisp, you can still understand the idea behind fold/reduce.