Flashback to April 2016!

Tyrannosaurus Rex

Tyrannosaurus Rex

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 is`n / 2`

if the preceding number is even. It’s`3 * n + 1`

if the preceding number is odd. The third number is computed with identical language, but using the second number instead of`n`

. And so is the fourth, fifth, and beyond. The final number is 1. Write in Ruby, C, or pseudocode, write a function`collatz`

that generates a Collatz sequence given a starting`n`

. For example,`collatz 10`

yields`[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 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)

- 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:

- 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
`fullnames`

that 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,

- April 2017
- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- October 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- July 2011
- January 2011

- 3d
- algorithms
- aphasia
- art
- blackbox
- blender
- buster
- code
- courses
- cs145
- cs245
- cs318
- cs330
- cs352
- cs396
- cs436
- cs455
- cs491 mobile
- exams
- experiments
- failures
- fall 2011
- fall 2012
- fall 2013
- fall 2014
- fall 2015
- fall 2016
- fish vision
- gallery
- gamedev for learning
- gamedev_cse
- gamedev2
- gamedev3
- games
- git
- graphics
- honors 304.503
- honors gamedev
- howto
- keystrokes
- labs
- lectures
- madeup
- meta
- mobile
- mutt
- nature
- nbsn
- outreach
- pop computer science
- postmortems
- programming languages
- public
- ratorvaders
- reader animated
- reading
- research
- responses
- semesters
- software
- specchecker
- specifications
- spring 2012
- spring 2013
- spring 2014
- spring 2015
- spring 2016
- spring 2017
- talks
- teaching
- travel
- Uncategorized
- unity
- vim
- writing
- wrong number

## Leave a Reply