Higher Order Functions

The last few years I have been spending my spare time with languages like Scheme, Ruby, Haskell and Erlang. The reason I’m doing this is that the expressiveness of these languages is a lot higher than that of my work language, Java. I’m able to do more with less code. And the reason for this is higher order functions. Higher order functions is enabled by having functions as first class citizens of the language.

Map

The first of the higher order funtions is map. Map takes two arguments a function and a list and returns a new list with the result of applying the funtion to every element of the list. Map raises the abstraction of list iteration by allowing me to focus on converting one element of this into one element of that instead of worrying about how to convert a list of this into a list of that. It simplifies my job.

; Map in Scheme
(define (map f l)
(if (null? l)
 '()
 (cons (f (car l)) (map f (cdr l)))))

>(map plusone '(1 2 3 4))
(2 3 4 5)

-- Map in Haskell
map f []     = []
map f (x:xs) = f x : map f xs

> map (+ 1) [1..8]
[2,3,4,5,6,7,8,9]

Filtering

Map always returns a list of the same length as the one given as argument. Sometime I only want the elements that fulfill some criteria to be returned. This calls for filtering.

; Filter in Scheme
(define (filter p l)
 (cond
   ((null? l) '())
   ((p (car l)) (cons (car l) (filter p (cdr l))))
   (else (filter p (cdr l)))))

>(filter even? '(1 2 3 4 5 6))
(2 4 6)

-- Filter in Haskell
filter p [] = []
filter p (x:xs)
 | p x = x : filter p xs
 | otherwise = filter p xs      

> fil odd [1..8]
[1,3,5,7]

Reduce

Another thing commonly done with lists is to combine the arguments into one value. This can be done with reduce.

; Reduce in Scheme
(define (reduce op l)
 (if (null? (cdr l))
   (car l)
   (op (car l) (reduce op (cdr l)))))

>(reduce + '(1 2 3 4))
10
>(reduce - '(1 2 3 4))
2

-- Reduce in Haskell
reduce op (x:[]) = x
reduce op (x:xs) = (op x (reduce op xs))

> reduce (+) [1..4]
10

Compose

We now have the ability to transform lists by mapping a function to every element or by filtering the elements according to some predicate function. We are also able to reduce a list by combining the elements with a binary function. We would also like the ability to create new functions by combining two functions and this is where compose comes in:

; Compose in Scheme
(define (compose f g)
 (lambda (x)
   (f (g x))))

; Add as a higher order function
(define odd? (compose even? plusone))

> (odd? 3)
#t

-- Compose in Haskell
compose :: (b -> c) -> (a -> b)  -> (a -> c)
compose f g = \x -> f (g x)

-- Odd as a higer order function
odd = compose even plusone

> compose even plusone
10

It is important that the type signatures of the functions set to compose match as can be seen in the type definition of the Haskell example above. The type returned by function g must be the input of function f.

Currying

Another method of creating new methods is currying¹. Currying means creating new functions by only suppling part of the required arguments to the function. Instead of failing a new function is created. This is directly supported in Haskell, but must be done explicitly in Scheme (or by use of macros).

-- Currying in Haskell  
-- + is a binary function but only given one parameter it returns a closure.
plusone = (+ 1)

> plusone 3
4   

; Currying in Scheme
(define (curry f . args)
 (lambda x
   (apply f (append args x))))

> (define plusone (curry + 1))
> (plusone 3)
4

Const

In order to combine useful functions it is sometimes necessary to have simplifying functions and const is as simple as they come. const returns the same value no matter what argument it is given.

; Const in Scheme
(define (const k)
 (lambda (x) k))

> (define five (const 5))
> (five 6)
5

-- Const in Haskell
const k = \x -> k

five = const 5

> five 6
5

Even Higher Order Functions

All the functions above, there are more in any good book on functional programming, gives me the ability to produce many other functions simply by combining them together.

; Length in Scheme
(define length
 (compose (curry reduce +) (curry map (const 1))))

> (length '(1 2 3 4))
4


-- Length in Haskell
length = compose (reduce (+)) (map (const 1))

> length [1, 2, 3, 4, 5, 6]
6
      

To be able to raise the level of abstraction like this is what makes programming fun and I long for it when using rigid languages like Java.

¹ The technique was named by Christopher Strachey after logician Haskell Curry, though it was invented by Moses Schönfinkel and Gottlob Frege.