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 ++ ", 

LYAH Chapter 4 - Syntax in Functions

Syntax in Functions

• Pattern matching
• specifying patterns to which some data should conform and then checking to see if it does and deconstructing the data according to those patterns.
• Define separate function bodies for different patterns. 
• Can pattern match on any data type — numbers, characters, lists, tuples, etc.
• Patterns will be checked from top to bottom
• Order is important when specifying patterns and it's always best to specify the most specific ones first and then the more general ones later.
• Non-exhaustive patterns fail
• _ means the same thing as it does in list comprehensions.
• Can also pattern match in list comprehensions.
• Should a pattern match fail, it will just move on to the next element.
• If you want to bind to several variables we have to surround them in parentheses. 
• error function takes a string and generates a runtime error - causes the program to crash.
• Note that (x:[]) == [x] and  (x:y:[])  == [x,y] 
• We can't rewrite (x:y:_) with square brackets because it matches any list of length 2 or more.
• empty list - also known as the edge condition. 
• as patterns - a name and an @ in front of a pattern. 
• For instance, the pattern xs@(x:y:ys) lets you get the whole list via xs 
• capital "" = "Empty string, whoops!"  
• capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]  
• ghci> capital "Dracula" --> "The first letter of Dracula is D"  
• Can't use ++ in pattern matches. If you tried to pattern match against (xs ++ ys), what would be in the first and what would be in the second list? It doesn't make much sense. It would make sense to match stuff against (xs ++ [x,y,z]) or just (xs ++ [x]), but because of the nature of lists, you can't do that.
• Guards, guards!
• patterns ensure a value conforms to some form and deconstruct it
• guards test whether some property of a value (or several of them) are true or false. 
• otherwise is defined simply as otherwise = True and catches everything. 
• If all the guards of a function evaluate to False, evaluation falls through to the next pattern. That's how patterns and guards play nicely together. If no suitable guards or patterns are found, an error is thrown.
• There's no = right after the function name and its parameters, before the first guard.
• Guards can also be written inline, it's less readable, even for very short functions.
• Note: Not only can we call functions as infix with backticks, we can also define them using backticks.
• Where!?
• Put the keyword where after the guards (usually it's best to indent it as much as the pipes are indented) and then define several names or functions. 
• It improves readability by giving names to things.
• Can make our programs faster since stuff like our bmi variable here is calculated only once. 
• The names we define in the where section of a function are only visible to that function
• Align names at a single column otherwise Haskell gets confused because then it doesn't know they're all part of the same block.
• where bindings aren't shared across function bodies of different patterns. If you want several patterns of one function to access some shared name, you have to define it globally.
• You can also use where bindings to pattern match
• where bmi = weight / height ^ 2  
•       (skinny, normal, fat) = (18.5, 25.0, 30.0)  
• Can also define functions in where blocks.
• calcBmis xs = [bmi w h | (w, h) <- xs]  
•     where bmi weight height = weight / height ^ 2  
• The reason we had to introduce bmi as a function in this example is because we can't just calculate one BMI from the function's parameters. We have to examine the list passed to the function and there's a different BMI for every pair in there.
• where bindings can also be nested. It's a common idiom to make a function and define some helper function in its where clause and then to give those functions helper functions as well, each with its own where clause.
• Let it be
• Where bindings are a syntactic construct that let you bind to variables at the end of a function and the whole function can see them, including all the guards. 
• Let bindings let you bind to variables anywhere and are expressions themselves but don't span across guards. 
• let bindings can be used for pattern matching. 
• cylinder r h = 
•     let sideArea = 2 * pi * r * h  
•         topArea = pi * r ^2  
•     in  sideArea + 2 * topArea  
• The form is let <bindings> in <expression>. 
• The names that you define in the let part are accessible to the expression after the in part. 
• As you can see, we could have also defined this with a where binding. 
• Names are also aligned in a single column. 
• Difference with where is that let bindings are expressions themselves. 
• where bindings are just syntactic constructs. 
• Just like the if else statement is an expression that can go almost anywhere
• ghci> 4 * (let a = 9 in a + 1) + 2  -->  42  
• Can also be used to introduce functions in a local scope:
• ghci> [let square x = x * x in (square 5, square 3, square 2)]  -->  [(25,9,4)]  
• Can separate them with semicolons.
• ghci> (let a = 100; b = 200; c = 300 in a*b*c, let foo="Hey "; bar = "there!" in foo ++ bar)  -->  (6000000,"Hey there!")  
• You don't have to put a semicolon after the last binding but you can if you want. 
• Pattern matching with let bindings are very useful for quickly dismantling a tuple into components and binding them to names and such.
• ghci> (let (a,b,c) = (1,2,3) in a+b+c) * 100  -->  600  
• You can also put let bindings inside list comprehensions. 
• calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2]  
• We include a let inside a list comprehension much like we would a predicate, only it doesn't filter the list, it only binds to names. 
• The names defined in a let inside a list comprehension are visible to the output function and all predicates and sections that come after of the binding. 
• calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]  
• We can't use the bmi name in the (w, h) <- xs part because it's defined prior to the let binding.
• We omitted the in part of the let binding when we used them in list comprehensions because the visibility of the names is already predefined there. 
• However, we could use a let in binding in a predicate and the names defined would only be visible to that predicate. 
• The in part can also be omitted when defining functions and constants directly in GHCi. If we do that, then the names will be visible throughout the entire interactive session.
• Case expressions
• Case expressions are expressions much like if else expressions and let bindings. 
• Can do pattern matching. 
• Pattern matching on parameters in function definitions is actually syntactic sugar for case expressions. 
• These two pieces of code do the same thing and are interchangeable:
• head' [] = error "No head for empty lists!"  
• head' (x:_) = x  
• 
  
• head' xs = case xs of [] -> error "No head for empty lists!"  
•                       (x:_) -> x  
• case expression of pattern -> result  
•                    pattern -> result  
•                    pattern -> result  
•                    ...  
• expression is matched against the patterns. 
• If it falls through the whole case expression and no suitable pattern is found, a runtime error occurs.
• Case expressions can be used pretty much anywhere. For instance:
• describeList xs = "The list is " ++ case xs of [] -> "empty."  
•                                                [x] -> "a singleton list."   
•                                                xs -> "a longer list."  
• They are useful for pattern matching against something in the middle of an expression. 
• Could also define like this:
• describeList xs = "The list is " ++ what xs  
•     where what [] = "empty."  
•           what [x] = "a singleton list."  
•           what xs = "a longer list."  

Questions

1. Why can we pattern match against cons (:) but not (++)?  Because (:) is a constructor but (++) is a function??
1. Why can't we match stuff against (xs ++ [x,y,z]) or (xs ++ [x]) ??
2. Why can't we use an as-pattern in a where clause?
   e.g.: where all@(skinny, normal, fat) = (18.5, 25.0, 30.0)
• It works!  We can use as-pattern in a where clause.

Monad examples

http://www.haskell.org/haskellwiki/Simple_monad_examples

Just 5 >>= (\ x -> if (x == 0) then fail "zero" else Just (x + 1) )

http://hackage.haskell.org/packages/archive/base/4.4.1.0/doc/html/Data-Maybe.html#t:Maybe
data Maybe a = Nothing | Just a
instance Monad Maybe