## Higher-order functions in Haskell

### November 28, 2014

Dear blog, I’ve got the hots for Haskell.

Its terse syntax is intimidating at first, but as you keep exploring, you start seeing its beauty and even possible ways to write a Hello World program.

But let’s start from the easy bits: this language makes it trivial to compose functions, and in a sense specialize the bare language to represent more closely the semantics of the computational problem at hand.

One of the most basic higher order functions is `map`

, which takes a unary function *f* and a list *l* and returns a new list, made of mapping *f* onto every element of *l*:

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

Silly examples!

> map (+1) [1,2,3] [2,3,4] > map (\c -> if c=='o' then 'i' else c ) "potatoes" "pitaties"

Similarly, the right ‘fold’ operation (called ‘reduce’ in other languages) `foldr`

takes a binary function *f*, a starting object *v* and a list *(x:xs)* , and maps *f* across the elements of *(x:xs)* recursively:

foldr :: (t -> t1 -> t1) -> t1 -> [t] -> t1 foldr f v [] = v foldr f v (x:xs) = f x (foldr f v xs)

Binary functions? We’re not restricted to arithmetic operations! If we consider f in the example above as the functional composition operator `(.)`

, and the starting element v being the identity *function* `id`

, the Haskell typechecker will infer that `foldr (.) id`

just requires a list of `a -> a`

functions (i.e. that share the same type signature as `id`

, in this case) and an element to start with!

So here’s `compose`

:

compose :: [a -> a] -> a -> a compose = foldr (.) id

This idea of representing n-ary functions as daisy-chains of unary elements is called “currying“, and is crucial for reasoning about programs, as we can see in the above example.

Functional composition is implemented as follows, where “\u -> .. body .. ” is the idiom for anonymous (lambda) functions of a variable u:

(.) :: (b -> c) -> (a -> b) -> a -> c (.) f g = \x -> f (g x)

Another thing of beauty is `unfold`

, which serves to build data structures up from a prototype element.

In this case, it’s specialized to the List monad, so the neutral element is the empty list `[]`

and the structure constructor is the list concatenation operation `(:)`

.

unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b] unfold p h t x | p x = [] | otherwise = h x : unfold p h t (t x)

See the type signature? We need a function from a domain to Booleans (a “decision” function *p*), two functions *h* and *t* that are applied to the head and to the recursion tail, respectively.

Unfold can be generalized to arbitrary recursive structures, such as trees, heaps etc.

As a quick example, a function that takes a positive integer and returns its digits as a list can be very compactly formulated in terms of *unfold* (however, leading zeroes are discarded):

toDigits :: Integer -> [Integer] toDigits = reverse . unfold (==0) (`mod` 10) (`div` 10)

> toDigits 29387456 [2,9,3,8,7,4,5,6]

Next up: Monoids! Functors! Monads! “Hello World” ! and other abstract nonsense.