19.md

Higher order functions

Fold

Folds are used to process data structures to a single return value. Some languages call it reduce.

Imperative example

Let's start with an example in python where fold could be used.

evens_as_string = ""
for num in range(6):
  if num%2 == 0:
    evens_as_string = evens_as_string + str(num)

print(evens_as_string)

This small snippet converts even numbers to string and concatenates them. It does two things:

• iterates over a data structure
• accumulates a value as it iterates through the structure

Foldr

Let's have a look at the fold right function.

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

The foldable typeclass describes types that can be folded. List is an instance of the foldable typeclass. Replacing t a with [a] might help in reading the type signature.

Let's go through the parameters one-by-one:

• (a -> b -> b) : This is a function that accepts a value from the foldable and a value that has the same type as the result of the fold. It combines one element of the data structure with the values processed so far.
• b : This is the type that is the result of the fold. This value is used by the combinator function the first time it is called.
• t a : This is the data structure that we are folding.

Let's see the python code translated to Haskell using foldr.

f :: (Show a, Integral a) => a -> String -> String
f n acc
  | even n = (show n) ++ acc
  | otherwise = acc

foldr f "" [1..6]

The combinator function converts the content of the foldable to string and concatenates it to the already combined value. The second parameter of foldr (the empty String) is combined with the last item of the foldable.

So foldr does something like this:

--foldr
(show 2 ++ (show 4 ++ (show 6 ++ "")))

Exercise

• Create a list with type [Knight] and using foldr implement the following function.

concatColours :: Foldable t => t Knight -> String

Extra exercise

• Implement myfoldr.