CSC302 2011S, Class 22: Haskell (1)

Overview:
* Haskell: An Introduction.
* Lab.

Admin:
* Missing (excused): AC, AH, JR
* I brought you back a bit of swag from the conference.
* This is Glorious Haskell Week.
* I anticipate distributing the mid-semester exam on Wednesday.
* Sorry for the confusion on the drop-box for assignment 7.  Email was fine.
* The videos should be on reserve in Burling.

Stories from the conference

* F#
  [ for X in [1..10] => yield X*X ]
* Donald Knuth is a Grinnell alum
* Luis Von Ahn
  * The ESP game
  * Captchas
'   "I hear that the captcha sites use an IP-based filter.  How do you
     get around it?"
  * duolingo.com

Haskell
* What are "the big ideas" in Haskell
  * Pure and functional
    * Pure: Functions don't modify state; The same function, applied to
      the same arguments, gives the same result.
      * Lets you cache previously computed results
  * And lazy!
    * Lets you define infinite lists (and extract portions)
    * Delays the value of an expression until its value is needed
      let throw-away-second x y = x
      throw-away-second 1 (permutation-sort (iota 100000))
    * Theorem: If you can compute a value using any evalaution order,
      you can compute it using lazy evaluation (just maybe slower)
      if true x y = x
      if false x y = y
      car (cons x y) = x
      cdr (cons x y) = y
  * Strongly and statically typed with nice ways to unpack types
    * And really good type inference, that also works with functions
  * You can still do side-effects (although we have not yet learned
    how)

* What are some "medium ideas"
  * Lets you return multiple values from a function through a tuple
    which is easy to take apart.
  * Optimized for tail recursion.  (Well, duh.
  * Pattern matching
  * List comprehensions
  * Design-by-committee

Lab

Reflection
* Different Fibonaccis give different results!  Why?
* Suppose we defined a random function for simulation and it had
  the signature Int -> Int
*Main> rand 5
3
*Main> rand 5
3
*Main> rand 5
3
* How can we write rand so that it gives different values?

* What's the type of 
take 0 l = []
take n (x:xs)= x:(take (n-1) xs)

* Option 1:
  take: (Int x [a]) -> [a]
* Option 2
  take: Int -> [Char] -> [Char]
* Option 3
  take: Int -> [a] -> [a]
* It's the third!
* Explain.  What does that mean?
  * a is "generic" - it means 'any type'
  * [a] means "list of any type"
  * How about the two arrows?

* Explain the following: