Lecture 7 - Higher Order Functions

What is a higher-order function?

A function that either takes functions as arguments and/or returns a function as a result.

Think about currying in terms of higher-order functions…

Wow - all Haskell functions are higher-order! Because in currying is the process of making a function that takes arguments all together into a function that takes one argument and returns a function!

What is the operator (.) and what does it do?

It takes two functions either side of it and composes them as follows:
odd = not . even
odd x = not (even x)

The type annotation for (.) is:
(.) :: (b → c) → (a → b) → (a → c)

What are some common higher order functions? (3) What do they do?

Map - which applies a function to every element
Filter - which keeps elements that satisfy a predicate
Foldr - which reduces a list to a value

What is the type annotation for map (on a list)?

map :: (a → b) → [a] → [b]

What about the type annotation for map on a binary tree?

bmap :: (a → b) → BinaryTree a → BinaryTree b

What is a functor?

A functor is a type class of mappable types (tuples, lists) that can have a function applied to every element/component of them.

So, fmap is like the functor generalisation of map. What is the type annotation for this?

fmap :: (a → b) → c a → c b

What are the two laws that functors must obey?

1 - Identity Law. If you fmap an identity function across a structure, the result will be the same as the input.
fmap id == id
2 - Composition Law. Composing two functions then mapping them should output the same as mapping one after the other.
fmap (f . g) = = fmap f . fmap g

Can you prove the identity law?

fmap id (Cons x xs)
= Cons (id x) (fmap id xs)
= Cons x xs

What is a functor instance?

You define a functor instance for your own data type which implements the Functor type by providing a valid fmap function.

How would you define a functor instance for a list?

data List a = Nil | Cons a (List a)
instance Functor List where
fmap _ Nil = Nil

fmap f (Cons x xs) = Cons (f x) (fmap f xs)

How would you define a functor instance for a binary tree?

data BinaryTree a = Leaf a | Node a (BinaryTree a) (BinaryTree a)
instance Functor BinaryTree where
fmap f (Leaf a) = Leaf (f a)
fmap f (Node a l r) = Node (f a) (fmap f l) (fmap f r)