Chapter 5: Recursion

Learn You a Haskell for Great Good!

Hello recursion!

  • Do computation in Haskell by declaring what something is instead of declaring how you get it.

Maximum awesome

  • Here is an example of maximum function:
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs)
    | x > maxTail = x
    | otherwise = maxTail
    where maxTail = maximum' xs
  •  The function check base or edge condition of empty list and singleton. Then it check if the head is more than the maximum of the rest of the list and recursive through the tail.
maximum' :: (Ord a) => [a] -> a
maximum' [] = error "maximum of empty list"
maximum' [x] = x
maximum' (x:xs) = max x (maximum' xs)
  • A different representation use max function
maximum'[2,5,1] = max ~2 \left( maximum'[5,1] = max ~3 \left( maximum[1] = ~1 \right) \right) 

A few more recursive function

  • The take function return the number of element from a list. Take 0 or less will return an empty list
take' :: (Num i, Ord i) => i -> [a] -> [a]
take' n _
    | n <= 0 = []
take' _[]    = []
take' n (x:xs) = x : take' (n-1) xs
  • Num is not a subclass of Ord. When doing addition and subtraction and comparison, both are needed.

Quick, sort!

  • In quick sort, take a pivot, x, and put all element smaller than x before x and bigger than x after x.
quicksort' :: (Ord a) => [a] -> [a]
quicksort' [] = []
quicksort' (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ biggerSorted

Thinking recursively

  • Start with an edge case where the recursion doesn’t make sense and then use function to make a smaller problem that can be solve by the function again.
Advertisements