teaching machines

CS 330 Lecture 20 – Recursion, Cases, and Pattern Matching

March 17, 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 is an exercise that I ask you to complete with a neighbor:

And here are the problems we’ll solve:

  1. Let’s write a Collatz conjecture checker. The Collatz conjecture spins around transforming an integer using this logic:
    if x is even
      x / 2
    else
      3 * x + 1
    The conjecture is the notion that in doing this repeatedly, you will eventually reach 1, no matter what the starting x is. Let’s return the list of numbers in the Collatz sequence for a given starting x. If it doesn’t stop, well, we won’t return at all. First, we might right this in Ruby like so:
    def collatz x
      nums = [x]
      while x != 1
        if x % 2 == 0
          x /= 2
        else
          x = 3 * x + 1
        end
        nums << x
      end
      nums
    end
    Now for Haskell. Guess what? Haskell doesn’t have loops. Isn’t that crazy? What can we use instead? Recursion! Here’s a first attempt:
    collatz x = 
      if x == 1
        [1]
      else
        if mod x 2 == 0
          x : collatz (div x 2)
        else
          x : collatz (3 * x + 1)
    I don’t think I would write this any other way, but because everything in Haskell returns a value, we could factor out the cons:
    collatz x = 
      if x == 1
        [1]
      else
        x : if mod x 2 == 0
              collatz (div x 2)
            else
              collatz (3 * x + 1)
  2. Let’s write a function to determines if a list contains an element. Our first attempt will use only ideas we’ve already seen:
    contains :: [a] -> Bool
    contains needle haystack =
      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 let’s us focus on one case at a time. In my opinion, it is the pinnacle of clarity.

Here’s your TODO list:

See you next time!

Sincerely,