Lecture 14-2

Higher Order Functions

A higher order function is a function that:

apply_twice :: (a -> a) -> a -> a
apply_twice f input = f (f input)

> apply_twice tail [1,2,3,4]
> [3,4]

This function takes a function and an input as an argument and then uses the supplied function twice on the supplied argument.

An example including currying (partial application):

> apply_twice (drop 2) [1,2,3,4,5]
> [5]

A caveat of using this function is that it must return the same type that is is given.

Function composition applies one function to the output of another

compose :: (b -> c) -> (a -> b) -> a -> c
compose f g input = f (g input)

> compose (+1) (*2) 4
> 9

This is the same thing as applying a function to another function.

The type of . is:

(.) :: (b -> c) -> (a -> b) -> a -> c

The . operator is an infix operator called compose. To complete the same action as will the compose function write:

> ((+1) . (*2)) 4
> 9

This means to apply the left function on the argument and then the right function on the result of the previous function.

f list = length (double (drop_evens (tail list)))

f' list = (length . double . drop evens . tail) list

As you can see from the two different implementations; the use of . removes the need for nested brackets, however:

evaluate :: (a -> b) -> a -> b
evaluate f input = f input

The $ operator is exactly the same as evaluate. $ is infix.

The $ operator has the lowest precedence of any operator. As a result it can be used in place of brackets:

((*2) . length) [1,2,3,4]
(*2) . length $ [1,2,3,4]

length ([1,2,3] ++ [4,5,6])
length $ [1,2,3] + [4,5,6]

 applyThrice :: (a -> a) -> a -> a
 applyThrice f x = f . f . f $ x

 f :: (Ord a, Enum a) => [a] -> a
 f x = succ . sum . tail . tail $ x