LYAH Chapter 5 - Recursion

Recursion

• Hello recursion!
• Function is applied inside its own definition.
• Definitions in mathematics are often given recursively. E.g. fibonacci:
• F(0) = 0 and F(1) = 1
• F(n) = F(n-1) + F(n-2)
• Edge condition - an element defined non-recursively 
• Very concise and elegant solutions to problems by thinking recursively.
• Declare what something is instead of declaring how you get it - no while loops or for loops
• Maximum awesome
• maximum' [] = error "maximum of empty list"  
• maximum' [x] = x  
• maximum' (x:xs)   
•     | x > maxTail = x  
•     | otherwise = maxTail  
•     where maxTail = maximum' xs  
• Pattern matching goes great with recursion
• Use pattern matching to split a list into a head and a tail - very common list idiom
• Using max:
• maximum' :: (Ord a) => [a] -> a  
• maximum' [] = error "maximum of empty list"  
• maximum' [x] = x  
• maximum' (x:xs) = max x (maximum' xs)  
• How's that for elegant! In essence, the maximum of a list is the max of the first element and the maximum of the tail.
• A few more recursive functions
• replicate 
• replicate' :: (Num i, Ord i) => i -> a -> [a]  
• replicate' n x  
•     | n <= 0    = []  
•     | otherwise = x:replicate' (n-1) x  
• We used guards here instead of patterns because we're testing for a boolean condition.
• Note: Num is not a subclass of Ord. That means that what constitutes for a number doesn't really have to adhere to an ordering. So that's why we have to specify both the Num and Ord class constraints when doing addition or subtraction and also comparison.
• take
• takes a certain number of elements from a list. For instance, take 3 [5,4,3,2,1] will return [5,4,3]. If we try to take 0 or less elements from a list, we get an empty list. Also if we try to take anything from an empty list, we get an empty list. Notice that those are two edge conditions right there. So let's write that out:
• take' :: (Num i, Ord i) => i -> [a] -> [a]  
• take' n _  
•     | n <= 0   = []  
• take' _ []     = []  
• take' n (x:xs) = x : take' (n-1) xs  
• We're using _ to match the list because we don't really care what it is in this case. Also
• We use a guard, but without an otherwise part. That means that if n turns out to be more than 0, the matching will fall through to the next pattern. 
• The second pattern indicates that if we try to take anything from an empty list, we get an empty list. The third pattern breaks the list into a head and a tail. And then we state that taking n elements from a list equals a list that has x as the head and then a list that takes n-1 elements from the tail as a tail. Try using a piece of paper to write down how the evaluation would look like if we try to take, say, 3 from [4,3,2,1].
• reverse 
• reverse' :: [a] -> [a]  
• reverse' [] = []  
• reverse' (x:xs) = reverse' xs ++ [x]  
• Because Haskell supports infinite lists, our recursion doesn't really have to have an edge condition. But if it doesn't have it, it will either keep churning at something infinitely or produce an infinite data structure, like an infinite list. The good thing about infinite lists though is that we can cut them where we want. 
• repeat 
• takes an element and returns an infinite list that just has that element. A recursive implementation of that is really easy, watch.
• repeat' :: a -> [a]  
• repeat' x = x:repeat' x  
• Calling repeat 3 will give us a list that starts with 3 and then has an infinite amount of 3's as a tail. So calling repeat 3 would evaluate like 3:repeat 3, which is 3:(3:repeat 3), which is3:(3:(3:repeat 3)), etc. repeat 3 will never finish evaluating, whereas take 5 (repeat 3) will give us a list of five 3's. So essentially it's like doing replicate 5 3.
• zip
• takes two lists and zips them together. zip [1,2,3] [2,3] returns [(1,2),(2,3)], because it truncates the longer list to match the length of the shorter one. How about if we zip something with an empty list? Well, we get an empty list back then. So there's our edge condition. However, zip takes two lists as parameters, so there are actually two edge conditions.
• zip' :: [a] -> [b] -> [(a,b)]  
• zip' _ [] = []  
• zip' [] _ = []  
• zip' (x:xs) (y:ys) = (x,y):zip' xs ys  
• First two patterns say that if the first list or second list is empty, we get an empty list. The third one says that two lists zipped are equal to pairing up their heads and then tacking on the zipped tails. Zipping[1,2,3] and ['a','b'] will eventually try to zip [3]with []. The edge condition patterns kick in and so the result is (1,'a'):(2,'b'):[], which is exactly the same as[(1,'a'),(2,'b')].
• elem
• takes an element and a list and sees if that element is in the list. The edge condition, as is most of the times with lists, is the empty list. We know that an empty list contains no elements, so it certainly doesn't have the droids we're looking for.
• elem' :: (Eq a) => a -> [a] -> Bool  
• elem' a [] = False  
• elem' a (x:xs)  
•     | a == x    = True  
•     | otherwise = a `elem'` xs   
• Pretty simple and expected. If the head isn't the element then we check the tail. If we reach an empty list, the result is False.
• Quick, sort!
• Sorting list of Ord items. 
• Takes upwards of 10 lines to implement quicksort in imperative languages, the implementation is much shorter and elegant in Haskell - poster child, cheesy.
• So, the type signature is going to be quicksort :: (Ord a) => [a] -> [a]. 
• Edge condition - Empty list - a sorted empty list is an empty list.
• Main algorithm: 
• a sorted list is a list that has: all the values smaller than or equal to head in front (and those values are sorted), then comes the head in the middle and then come all the values that are bigger than head (they're also sorted). 
• Notice that we defined it using the verb is to define the algorithm instead of saying do this, do that, then do that .... That's the beauty of functional programming!
• 1. quicksort :: (Ord a) => [a] -> [a]  
  2. quicksort [] = []  
  3. quicksort (x:xs) =   
  4.     let smallerSorted = quicksort [a | a <- xs, a <= x]  
  5.         biggerSorted = quicksort [a | a <- xs, a > x]  
  6.     in  smallerSorted ++ [x] ++ biggerSorted  
• Let's give it a small test run to see if it appears to behave correctly.
• 1. ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]  
  2. [1,2,2,3,3,4,4,5,6,7,8,9,10]  
  3. ghci> quicksort "the quick brown fox jumps over the lazy dog"  
  4. "        abcdeeefghhijklmnoooopqrrsttuuvwxyz"  
• So if we have, say [5,1,9,4,6,7,3] and we want to sort it, this algorithm will first take the head, which is 5 and then put it in the middle of two lists that are smaller and bigger than it. 
• So at one point, you'll have[1,4,3] ++ [5] ++ [9,6,7]. 
• In quicksort, an element that you compare against is called a pivot - we chose the head because it's easy to get by pattern matching. 
• Thinking recursively
• Pattern:
• Define an edge case, then define a function that does something between one element and the function applied to the rest. 
• It doesn't matter if it's a list, a tree or any other data structure. 
• sum - the first element of a list plus the sum of the rest of the list. 
• product - the first element of the list times the product of the rest of the list. 
• length - one plus the length of the tail of the list.
• Edge cases:
• Lists - empty list. 
• Trees - node that doesn't have any children.
• It's similar when you're dealing with numbers recursively. 
• Some number and the function applied to that number modified. 
• factorial - the product of a number and the factorial of that number minus one. 
• Often edge case value is the identity.  E.g. Multiplication identity is 1.
• sum of empty list = 0.  Addition identity is 0.
• quicksort - empty list is edge case and identity - if you add an empty list to a list, you just get the original list back.
• Think about:
• when a recursive solution doesn't apply and see if you can use that as an edge case
• identities
• whether you'll break apart the parameters of the function (for instance, lists are usually broken into a head and a tail via pattern matching)
• on which part you'll use the recursive call

Questions

Why doesn't this work?

• qs'' [] = []
• qs'' (x:xs) = qs (filt (<=)) ++ [x] ++ qs (filt (>))
•     where filt f = filter (f x) xs

When this does:

• qs'' [] = []
• qs'' (x:xs) = qs (filt (<= x)) ++ [x] ++ qs (filt (> x))
•     where filt f = filter (f) xs

Observations


Haskell Debugging: http://www.haskell.org/haskellwiki/Debugging
hanoi a (source:spare:[dest]) | trace ((replicate a ' ') ++ "hanoi " ++ show a ++ " source:" ++ show source ++ ", spare:" ++ show spare ++ ",