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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s