Haskell Cheat Sheets - Recursion

haskell-cheat-sheets-recursion.md

[Haskell Cheat Sheets] (https://gist.github.com/vpayno/0a7db3ff9a4fac8774c5)

By Victor Payno

Recursion

Recursion happens when a function is called within its own definition and has a stop condition (otherwise it would never stop recursing). The stop condition is also referred to as the edge condition.

Recursion is an important part of Haskell because you define what something is rather than defining how to do get it.

Examples

• Fibonacci sequence

A Fibonacci number is the sum of the two previous Fibonacci numbers.

The 0th and 1st Fibonacci numbers are 0 and 1 respectively.

The formula is f(n) = f(n-1) + f(n-2).

fibonacci :: (Integral a) => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n - 1) + fibonacci (n - 2)

fibonacci 4
> 3

take 10 [fibonacci n | n <- [0..]]
> [0,1,1,2,3,5,8,13,21,34]

• Getting the maximum number from a list of numbers.

maximum' :: (Ord a) => [a] -> a
maximum' [] = error "tried to get the maximum of an empty list"
maximum' [x] = x
maximum' (x:xs)
    | x > maximumOfTail = x
    | otherwise = maximumOfTail
    where maximumOfTail = maximum' xs

maximum' [1,3,2]
> 3

1:[3,2] 1 > 3:[2] 3 > [2] 2 3 > 2 1 > 3 3

It can also be rewritten like this.

maximum'' :: (Ord a) => [a] -> a
maximum'' [] = error "tried to get the maximum of an empty list"
maximum'' [x] = x
maximum'' (x:xs) = max x (maximum'' xs)

• Using recursion instead of list comprehension to implement length [array].

length' :: [a] -> Integer
length' [x] = 1
length' (x:xs) = 1 + length' xs

length' [1,3..12]
> 6

We can also use recursion with guards.

Since Num isn't a subclass of Ord we have to specify both of them here so we can add them and compare them. Otherwise we would have to use another class like Integral.

replicate' :: (Num i, Ord i) => i -> a -> [a]
replicate' n x
    | n <= 0    = []
    | otherwise = x:replicate' (n - 1) x

replicate' 2 3
> [3,3]

Next we'll use recursion, patterns and guards to reimplement take. Since the first pattern with a guard does not have an otherwise part it falls through to the next pattern.

take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0   = []
take' _ []     = []
take' n (x:xs) = x : take' (n - 1) xs

take' 4 [1..]
> [1,2,3,4]

take' 0 [1..]
> []

take' 4 []
> []

Now we'll use recursion to reverse a list. Basically we swap the head (1st element) with the tail (all the other elements) of the list recursively until we end up with an empty list.

reverse' :: [a] -> [a]
reverse' [] = []
reverse' (x:xs) = reverse' xs ++ [x]

reverse' [1..10]
> [10,9,8,7,6,5,4,3,2,1]

The zip function can also be implemented using recursion. We use guards to deal with uneven sized lists.

zip' :: [a] -> [b] -> [(a,b)]
zip' _ [] = []
zip' [] _ = []
zip' (x:xs) (y:ys) = (x,y):zip' xs ys

zip' [1,3..10] [2,4..12]
[(1,2),(3,4),(5,6),(7,8),(9,10)]

This one is pretty cool. As soon as we find the element we are looking for we return True. Otherwise if we recurse all the way to the end (empty list) we return False.

elem' :: (Eq a) => a -> [a] -> Bool
elem' a [] = False
elem' a (x:xs)
    | a == x    = True
    | otherwise = a `elem'` xs

elem' 4 [1,2,3]
> False

elem' 4 [1,4,3]
> True

We still need to learn to sort our lists. Using the quicksort algorithm with Haskell is easy.

1. Take the head of the list.
2. Create a new list with numbers smaller or equal to the head.
3. Create a new list with numbers larger than the head.
4. Put the head in between both lists.
5. Repeat on the smaller list until we get an empty list (the tail).
6. Repeat on the larger list until we get an empty list (the tail).

[5,3,8,3,6,0,4,2,7,1] 5:[3,8,3,6,0,4,2,7,1] [3,3,0,4,2,1] 5 [6,8,7] 3:[3,0,4,2,1] 5 6:[8,7] [3,0,2,1] 3 [4] | 5 | [] 6 [8,7] 3:[0,2,1] 3 4:[] | 5 | :[] 6 8:[7] [0,2,1] | 3 3 4 5 6 | [7] 8 [] [0,2,1] | 3 3 4 5 6 | [7] | 8 [0,2,1] | 3 3 4 5 6 | 7:[] | 8 [0,2,1] | 3 3 4 5 6 | 7 | 8 [0,2,1] | 3 3 4 5 6 7 8 | 0:[2,1] | 3 3 4 5 6 7 8 | [] 0 [1,2] | 3 3 4 5 6 7 8 | 0 | 1:[2] | 3 3 4 5 6 7 8 | 0 | [] 1 [2] | 3 3 4 5 6 7 8 | 0 1 | [2] | 3 3 4 5 6 7 8 | 0 1 | 2:[] | 3 3 4 5 6 7 8 | 0 1 | 2 | 3 3 4 5 6 7 8 | [0,1,2,3,3,4,5,6,7,8]

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerList = quicksort [a | a <- xs, a <= x]
        largerList  = quicksort [a | a <- xs, a > x]
    in  smallerList ++ [x] ++ largerList

quicksort [5,3,8,3,6,0,4,2,7,1]
> [0,1,2,3,3,4,5,6,7,8]