Chase Kernan
Readings
Learn You a Haskell (http://learnyouahaskell.com/chapters):
(1) Introduction
(2) Starting Out (skim through the basic list functions and skip list comprehensions)
(3) Types and Typeclasses (skip references to list comprehensions, skim through the basic typeclasses)
(4) Syntax in Functions (only up to gaurds)
(9) Input and Output (only up to when)
Understanding Haskell Monads (http://ertes.de/articles/monads.html)
What is a purely functional programming language?
What does it mean to say that “Haskell is lazy”?
How does Haskell’s type system differ from Scheme’s?
What are homogeneous data structures and how do they relate to Haskell’s type system?
Try out a few list functions in the ghci interpreter.
Which of the following are valid Haskell lists? (It might be helpful to first read the “Types and Typeclasses” section first.
[(1, 2), (3, 4, 5), (6, 7)]
[(3.141, 2.718), (42.0, 0.0)]
[(“abc”, “de”), (“fg”, “hijk”)]
[(“foo”, 2), (3, “bar”)]
How does the Haskell -> notation relate to currying in λ-calculus?
What does (Eq a) => a -> [a] -> Bool mean (where Eq is the equality typeclass)?
Write a recursive function in Haskell that returns the n-th Fibonacci number.
What values match (x:y:_)?
What does the type IO () represent?
Why do we wrap input and output computations in the IO type?
Write a Haskell script that asks for the user’s name and prints “Hello, <user>” to the screen.
A language that is composed of only pure functions, i.e. functions that have no side-effects. When called with the same arguments, they will return the same value, every time. As a consequence, the language has referential transparency.
Haskell does not necessarily evaluate expressions in the order that you write them (or in any other predetermined ordering scheme found in imperative and some functional languages). Haskell is only guaranteed to evaluate an expression once it becomes necessary to perform some action (like printing an answer on the screen).
Haskell is statically typed, meaning that an identifier like length can only be used with correctly typed data (in this case, lists) and that any deviation from this use will cause a compile-time error. Scheme will similarly complain about such inappropriate uses of length, but only once that code is reached at runtime. Haskell also has a feature called type inference which will guess (usually correctly) at the type of your expressions at compile time. Haskell must know the type of your expressions at compile-time, while Scheme isn’t compiled at all.
Homogeneous data structures only contain elements of a single type (i.e. [1, 2, 3] is homogeneous, while [1, “a”, [3, 4]] is not). Since Haskell needs to know the type of every expression at compile-time, its data structures are (usually) homogeneous. If they weren’t homogeneous (or if we didn’t specify the type of each element explicitly), when we would try to pull out an element out of them, we would get data of unknown type! See tuples for an example of inhomogeneous data structures.
N/A
Keep in mind that lists are homogeneous, so they must be composed of elements of the same type and that tuples are of the same type as long as their elements have the same order of types (i.e. (1, “a”) is the same type as (3, “b”), but (“a”, 1) is not the same type as (1, “a”)).
No, (3, 4, 5) is not of the same type as (1, 2).
Yes.
Yes, “abc” and “fg” are both lists of characters. Lists of different lengths can be of the same type as long as they have elements of the same type. However, length is built into the type of tuples.
No.
In Haskell and in λ-calculus, a function that takes two parameters is equivalent to a function that takes one parameter and returns another function that takes one parameter (e.g. Int -> Int -> Int is the same as Int -> (Int -> Int)). Hence, there is no distinction between each of the parameters and the return type.
“(Eq a) =>” places a restriction on the type variable a: a must belong to the Eq typeclass. All members of the equality typeclass support the function == that checks to see if two instances of the type are equal. Thus, (Eq a) => a -> [a] -> Bool takes an item of a type that supports equality checking, a list of items of the same type, and returns a boolean.
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n-1) + fibonacci (n-2)
Any list with at least 2 elements in it.
IO () represents an input/output computation that returns nothing (i.e. the empty tuple). This is similar to the concept of higher-order functions in λ-calculus and Scheme, the IO type represents functions (or “computations”), not “actual” data like 1, 3.0, or “foo”.
To separate the “pure” from the “impure”. An IO instance necessarily represents something that causes a “side-effect.” When we chain together several of these instances together inside of a do block, we can treat them as if they were pure functions that take an implicit parameter describing the current “state of the world” and return something and the updated “state of the world”.
main = do
putStrLn "What is your name?"
name <- getLine
putStrLn ("Hello, " ++ name)
https://docs.google.com/presentation/d/1X3IBh3zdOQDZ9TIIiDChAimZ5Luz6t47wvLOOBicJm0/edit
Install the GHC Haskell compiler: sudo apt-get install ghc
Start reading Learn You a Haskell. Ask questions and try out the ghci interpreter! It’s a long reading, but it’s well-written and not too complicated (always a danger with Haskell tutorials).
If there’s time, start working in groups on the first question from the homework and put solutions up on the board.
Using the following functions to answer the quiz questions:
(define (flip func)
(lambda (a b) (func b a)))
(define (flop func use-a?)
(if use-a?
(lambda (a b) (func a))
(lambda (a b) (func b))))
(define (flip-flop func)
(flip (flop func (< (random) 0.5))))
(define pure?
(flip-flop (lambda (a) 4)))
Are flip and flop pure functions? Why or why not?
Is flip-flop a pure function? Why or why not?
Assuming random does not cause any side-effects, is pure? a pure function in Scheme? Why or why not?
Is a function composed of only other pure functions necessarily pure?
Yes, they are both pure functions. They produce no side-effects (or changes in “state”) and return pure functions. When called with the same arguments, they will return the same thing. Here, we define something to be the same if it behaves in the same way (Scheme might internally create different pointers, but these will not be explicitly noticeable by the user).
No, it’s not. random could have side-effects and half of the time, it will return a function where func is called with the first parameter, while in the other half it uses the second parameter. This breaks the condition that pure functions always return the same value given the same inputs.
Yes, since we can assume that random has no side-effects, we know that pure? is a function that takes two arguments and always returns 4, regardless of the output of random.
If we are writing in a language that is composed of only functions (i.e. no statements), then yes. If only pure functions are called within its body, then there is no opportunity for side-effects to be introduced. Similarly, in order for the output of the function to change when given the same inputs, one of its internal functions would have to change outputs. But, we know that it is composed of only pure functions, so that can’t happen.
Rewrite myAppend and myReverse from Homework 1 in Haskell (do not use the built-in functions).
Implement the recursive descent parser from Homework 11 in Haskell. To get started, you can use lambda.hs. You may find the documentation on built-in Haskell functions helpful: http://www.haskell.org/ghc/docs/latest/html/libraries/base/Prelude.html.
myAppend :: [a] -> [a] -> [a]
myAppend [] xs = xs
myAppend (head:rest) xs = head:(myAppend rest xs)
myAppend' :: [a] -> [a] -> [a]
myAppend' = flip $ foldr (:)
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (head:rest) = (myReverse rest) ++ [head]
myReverse' :: [a] -> [a]
myReverse' = foldl (flip (:)) []
See lambda_answers.hs