teaching machines

CS 330 Lecture 21 – More Recursion and Pattern Matching

March 29, 2017 by . Filed under cs330, lectures, spring 2017.

Dear students,

Today we solve more problems in Haskell together. Along the way we will discover some of the peculiarities of functional programming, like the lack of iteration, the supremacy of recursion, and the beauty of pattern matching:

Here are the problems we’ll solve:

  1. Last time we started to write a function to determine if a list contains an element. Our first attempt used simple conditionals and recursion:
    contains :: [a] -> Bool
    contains needle haystack =
      if haystack == [] then
        False
      else
        if head haystack == needle then
          True
        else
          contains needle $ tail haystack
    This is okay, but Haskell sports a really nice guard syntax that shows the decision structure that we often see in mathematics:
    contains needle haystack
      | head haystack == needle = True
      | otherwise = False
    A little shorter, right? Well, we also have a case statement in Haskell, which allows us to use pattern matching:
    contains needle haystack =
      case haystack of
        [] -> False
        (first : rest) -> first == needle || contains needle rest ] This doesn't seem better than the guards. However, Haskell allows us to rewrite this structure in a more digestable way: [code
    contains _ [] = False
    contains (first:rest) = first == needle || contains needle rest
    Under the hood these seemingly multiple definitions of contains get turned into a case statement. But this syntax lets us focus on one case at a time. In my opinion, it is the pinnacle of clarity.
  2. Let’s write sum to sum up a list of numbers in a similar way:
    sum [] = 0
    sum (first:rest) = first + sum rest
  3. Let’s write head':
    head' [] = error "Can't decapitate the empty list!"
    head' (first:rest) = first
    Notice that in the second case we don’t use rest at all. Haskell lets us acknowledge its irrelevance by blanking out the identifier name:
    head' (first:_) = first
    This feature is not unique to Haskell. Check out this from Ruby:
    def foo
      [1, 2]
    end
    first, second = foo
    
    The array returned by foo is destructured into first and second. Suppose we don’t need second:
    first, _ = foo
    
    If we didn’t explicitly express _, no destructuring would take place, and first would hold [1, 2]. C++ also allows us to disregard parameters simply by not naming them in the formal parameters:
    void foo(int a, int) {
      return f(a);
    }
    
    Why would you ever write a function to take in a certain number of parameters and then completely ignore one? That sounds ridiculous. Except when you get into the world of inheritance, where you don’t get to choose your parameters.
  4. Let’s write tail':
    tail' [] = error "Can't detorso the empty list!"
    tail' (_:rest) = rest
  5. Let’s write belows, which gives us back all elements of a list less than some threshold:
    belows [] = []
    belows threshold (first:rest)
      | first < threshold = first : belows rest
      | otherwise = belows rest
  6. Let’s write an enum-like structure:
    data Color = Red | Green | Blue | Yellow | Orange
  7. Let’s write eval, which evaluates an expression, just like we saw on the midterm. First, we need to create a hierarchy:
    data Expr =
      ExprInt Integer |
      ExprNegate Expr |
      ExprMultiply Expr Expr |
      ExprAdd Expr Expr
    Now we can define eval:
    eval :: Expr -> Integer
    eval (ExprInt n) = n
    eval (ExprNegate e) = -eval e
    eval (ExprMultiply e1 e2) = eval e1 * eval e2
    eval (ExprAdd e1 e2) = eval e1 + eval e2
    We need a crazy expression to test this on. How about (17 + 1) * -(0 + 2))?
    eval (ExprMultiply (ExprAdd (ExprInt 17) (ExprInt(1))) (ExprNegate (ExprAdd (ExprInt 0) (ExprInt 2)))
  8. Let’s write contains again, but this time let’s operate on a binary search tree:
    data Tree a =
      Leaf a |
      Branch (Tree a) a (Tree a)
    
    has :: Ord a => a -> Tree a -> Bool
    has needle (Leaf value) = value == needle
    has needle left value right
      | target == needle = True
      | target < needle = has needle left
      | otherwise = has needle right

See you next time, when we discuss the various ways we can define functions in Haskell!

Sincerely,