What are some interesting uses of higher-order functions?

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

Well, you notice that Haskell has no syntax for loops? No while or do or for. Because these are all just higher-order functions:

 map :: (a -> b) -> [a] -> [b]

 foldr :: (a -> b -> b) -> b -> [a] -> b

 filter :: (a -> Bool) -> [a] -> [a]

 unfoldr :: (b -> Maybe (a, b)) -> b -> [a]

 iterate :: (a -> a) -> a -> [a]

Higher-order functions replace the need for baked in syntax in the language for control structures, meaning pretty much every Haskell program uses these functions -- making them quite useful!

They are the first step towards good abstraction because we can now plug custom behavior into a general purpose skeleton function.

In particular, monads are only possible because we can chain together, and manipulate functions, to create programs.

The fact is, life is pretty boring when it is first-order. Programming only gets interesting once you have higher-order.

Answer 2

Many techniques used in OO programming are workarounds for the lack of higher order functions.

This includes a number of the design patterns that are ubiquitous in functional programming. For example, the visitor pattern is a rather complicated way to implement a fold. The workaround is to create a class with methods and pass in an element of the class in as an argument, as a substitute for passing in a function.

The strategy pattern is another example of a scheme that often passes objects as arguments as a substitute for what is actually intended, functions.

Similarly dependency injection often involves some clunky scheme to pass a proxy for functions when it would often be better to simply pass in the functions directly as arguments.

So my answer would be that higher-order functions are often used to perform the same kinds of tasks that OO programmers perform, but directly, and with a lot less boilerplate.

Answer 3

I really started to feel the power when I learned a function can be part of a data structure. Here is a "consumer monad" (technobabble: free monad over (i ->)).

data Coro i a
    = Return a
    | Consume (i -> Coro i a)

So a Coro can either instantly yield a value, or be another Coro depending on some input. For example, this is a Coro Int Int:

Consume $ \x -> Consume $ \y -> Consume $ \z -> Return (x+y+z)

This consumes three integer inputs and returns their sum. You could also have it behave differently according to the inputs:

sumStream :: Coro Int Int
sumStream = Consume (go 0)
    where
    go accum 0 = Return accum
    go accum n = Consume (\x -> go (accum+x) (n-1))

This consumes an Int and then consumes that many more Ints before yielding their sum. This can be thought of as a function that takes arbitrarily many arguments, constructed without any language magic, just higher order functions.

Functions in data structures are a very powerful tool that was not part of my vocabulary before I started doing Haskell.

Answer 4

Check out the paper 'Even Higher-Order Functions for Parsing or Why Would Anyone Ever Want To Use a Sixth-Order Function?' by Chris Okasaki. It's written using ML, but the ideas apply equally to Haskell.

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

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 7

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.

Answer 8

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 9

I'm a particular fan of higher-order memoization:

memo :: HasTrie t => (t -> a) -> (t -> a)

(Given any function, return a memoized version of that function. Limited by the fact that the arguments of the function must be able to be encoded into a trie.)

This is from http://hackage.haskell.org/package/MemoTrie

Answer 10

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 11

Here's a small paraphrased code snippet:

rays :: ChessPieceType -> [[(Int, Int)]]
rays Bishop = do
  dx <- [1, -1]
  dy <- [1, -1]
  return $ iterate (addPos (dx, dy)) (dx, dy)
...  -- Other piece types

-- takeUntilIncluding is an inclusive version of takeUntil
takeUntilIncluding :: (a -> Bool) -> [a] -> [a]

possibleMoves board piece = do
  relRay <- rays (pieceType piece)
  let ray = map (addPos src) relRay
  takeUntilIncluding (not . isNothing . pieceAt board)
    (takeWhile notBlocked ray)
  where
    notBlocked pos =
      inBoard pos &&
      all isOtherSide (pieceAt board pos)
    isOtherSide = (/= pieceSide piece) . pieceSide

This uses several "higher order" functions:

iterate :: (a -> a) -> a -> [a]
takeUntilIncluding  -- not a standard function
takeWhile :: (a -> Bool) -> [a] -> [a]
all :: (a -> Bool) -> [a] -> Bool
map :: (a -> b) -> [a] -> [b]
(.) :: (b -> c) -> (a -> b) -> a -> c
(>>=) :: Monad m => m a -> (a -> m b) -> m b

(.) is the . operator, and (>>=) is the do-notation "line break operator".

When programming in Haskell you just use them. Where you don't have the higher order functions is when you realize just how incredibly useful they were.

Answer 12

Here's a pattern that I haven't seen anyone else mention yet that really surprised me the first time I learned about it. Consider a statistics package where you have a list of samples as your input and you want to calculate a bunch of different statistics on them (there are also plenty of other ways to motivate this). The bottom line is that you have a list of functions that you want to run. How do you run them all?

statFuncs :: [ [Double] -> Double ]
statFuncs = [minimum, maximum, mean, median, mode, stddev]

runWith funcs samples = map ($samples) funcs

There's all kinds of higher order goodness going on here, some of which has been mentioned in other answers. But I want to point out the '$' function. When I first saw this use of '$', I was blown away. Before that I hadn't considered it to be very useful other than as a convenient replacement for parentheses...but this was almost magical...

Answer 13

One thing that's kind of fun, if not particularly practical, is Church Numerals. It's a way of representing integers using nothing but functions. Crazy, I know. <shamelessPlug>Here's an implementation in JavaScript that I made. It might be easier to understand than a Lisp/Haskell implementation. (But probably not, to be honest. JavaScript wasn't really meant for this kind of thing.)</shamelessPlug>

Answer 14

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.