What are some interesting uses of higher-order fun

Question

I'm currently doing a Functional Programming course and I'm quite amused by the concept of higher-order functions and functions as first class citizens. However, I can't yet think of many practically useful, conceptually amazing, or just plain interesting higher-order functions. (Besides the typical and rather dull map, filter, etc functions).

Do you know examples of such interesting functions?

Maybe functions that return functions, functions that return lists of functions (?), etc.

I'd appreciate examples in Haskell, which is the language I'm currently learning :)

Answer 1

There are several examples here: http://www.haskell.org/haskellwiki/Higher_order_function

I would also recommend this book: http://www.cs.nott.ac.uk/~gmh/book.html which is a great introduction to all of Haskell and covers higher order functions.

Higher order functions often use an accumulator so can be used when forming a list of elements which conform to a given rule from a larger list.

Answer 2

Higher-order functions are also required for currying, which Haskell uses everywhere. Essentially, a function taking two arguments is equivalent to a function taking one argument and returning another function taking one argument. When you see a type signature like this in Haskell:

f :: A -> B -> C

...the (->) can be read as right-associative, showing that this is in fact a higher-order function returning a function of type B -> C:

f :: A -> (B -> C)

A non-curried function of two arguments would instead have a type like this:

f' :: (A, B) -> C

So any time you use partial application in Haskell, you're working with higher-order functions.

Answer 3

One interesting and slightly crazy thing you can do is simulate an object-oriented system using a function and storing data in the function's scope (i.e. in a closure). It's higher-order in the sense that the object generator function is a function which returns the object (another function).

My Haskell is rather rusty so I can't easily give you a Haskell example, but here's a simplified Clojure example which hopefully conveys the concept:

(defn make-object [initial-value]
  (let [data (atom {:value initial-value})]
      (fn [op & args]
        (case op 
          :set (swap! data assoc :value (first args))
          :get (:value @data)))))

Usage:

(def a (make-object 10))

(a :get)
=> 10

(a :set 40)

(a :get)
=> 40

Same principle would work in Haskell (except that you'd probably need to change the set operation to return a new function since Haskell is purely functional)

Answer 4

It’s been mentioned that Javascript supports certain higher-order functions, including an essay from Joel Spolsky. Mark Jason Dominus wrote an entire book called Higher–Order Perl; the book’s source is available for free download in a variety of fine formats, include PDF.

Ever since at least Perl 3, Perl has supported functionality more reminiscent of Lisp than of C, but it wasn’t until Perl 5 that full support for closures and all that follows from that was available. And ne of the first Perl 6 implementations was written in Haskell, which has had a lot of influence on how that language’s design has progressed.

Examples of functional programming approaches in Perl show up in everyday programming, especially with map and grep:

@ARGV    = map { /\.gz$/ ? "gzip -dc < $_ |" : $_ } @ARGV;

@unempty = grep { defined && length } @many;

Since sort also admits a closure, the map/sort/map pattern is super common:

@txtfiles = map { $_->[1] }
            sort { 
                    $b->[0]  <=>     $a->[0]
                              ||
                 lc $a->[1]  cmp  lc $b->[1]
                              ||
                    $b->[1]  cmp     $a->[1]
            }
            map  { -s => $_ } 
            grep { -f && -T }
            glob("/etc/*");

or

@sorted_lines = map { $_->[0] }
                sort {
                     $a->[4] <=> $b->[4] 
                             ||
                    $a->[-1] cmp $b->[-1]
                             ||
                     $a->[3] <=> $b->[3]
                             ||
                     ...
                }
                map { [$_ => reverse split /:/] } @lines;

The reduce function makes list hackery easy without looping:

$sum = reduce { $a + $b } @numbers;

$max = reduce { $a > $b ? $a : $b } $MININT, @numbers;

There’s a lot more than this, but this is just a taste. Closures make it easy to create function generators, writing your own higher-order functions, not just using the builtins. In fact, one of the more common exception models,

try {
   something();
} catch {
   oh_drat();
};

is not a built-in. It is, however, almost trivially defined with try being a function that takes two arguments: a closure in the first arg and a function that takes a closure in the second one.

Perl 5 doesn’t have have currying built-in, although there is a module for that. Perl 6, though, has currying and first-class continuations built right into it, plus a lot more.

Answer 5

Joel Spolsky wrote a famous essay demonstrating how Map-Reduce works using Javascript's higher order functions. A must-read for anyone asking this question.

Answer 6

Martín Escardó provides an interesting example of a higher-order function:

equal :: ((Integer -> Bool) -> Int) -> ((Integer -> Bool) -> Int) -> Bool

Given two functionals f, g :: (Integer -> Bool) -> Int, then equal f g decides if f and g are (extensionally) equal or not, even though f and g don't have a finite domain. In fact, the codomain, Int, can be replaced by any type with a decidable equality.

The code Escardó gives is written in Haskell, but the same algorithm should work in any functional language.

You can use the same techniques that Escardó describes to compute definite integrals of any continuous function to arbitrary precision.