CS 330 Lecture 20 – Recursion, Cases, and Pattern Matching
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:
- CollatzThe first number of a Collatz sequence is an arbitrary integer
n. The second number isn / 2if the preceding number is even. It’s3 * n + 1if the preceding number is odd. The third number is computed with identical language, but using the second number instead ofn. And so is the fourth, fifth, and beyond. The final number is 1. Write in Ruby, C, or pseudocode, write a functioncollatzthat generates a Collatz sequence given a startingn. For example,collatz 10yields[10 5 16 8 4 2 1].
And here are the problems we’ll solve:
- 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 startingxis. Let’s return the list of numbers in the Collatz sequence for a given startingx. 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 endNow 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) - 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 haystackThis 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 acasestatement 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 restUnder the hood these seemingly multiple definitions ofcontainsget 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:
- Read chapters 3 and 4 of Learn You a Haskell for a Great Good!, which can be read freely online. On a quarter sheet, solve the following problems:
- Write a list comprehension that produces all possible passwords comprised of the 26 lowercase letters.
- Write a function
fullnamesthat accepts a list of first name/last name tuples. It returns a list in which each tuple has been joined together with an intervening space. For example,fullnames [("Mary", "Todd"), ("Abe", "Lincoln")]yields["Mary Todd", "Abe Lincoln"].
- Start on the Funfun assignment, which is due April 10.
See you next time!
Sincerely,
