PLE treasure hunt -- Haskell

Special forms

Why doesn't Haskell require these Scheme special forms?
  1. set!
  2. char?
  3. begin
  4. delay
  5. if


Write a flatten function in Haskell, like the one we wrote for Python. Try to use the declarative style.

Now write flatten using foldl.

Can we write superflatten in Haskell? (Hint: what would be its type?)

List comprehension

Haskell has a special feature for constructing lists, called a list comprehension:
[ f x | x <- xs, p x ]
In English: "compute the list of (f x) for all elements x in xs for which (p x) is true". For example:
[ x * 2 | x <- [1..4], x /= 3]   -- prints [2, 4, 8]

Why do you think Haskell made this a built-in construct? Can you "desugar" it into other, primitive forms? What if xs is an infinite list? (Remember Haskell is a lazy language.)

Programming with higher-order functions

Instead of mutation, Haskell uses higher-order functions. This leads to a rather different programming style. Does it recapture the expressiveness of side-effects?

Use the built-in functions ord, map, and foldl to define a function hash which hashes a string by summing the ASCII values of its characters. Try it out on "MSDOS 6.000" and "SYSTEM 7.0". (This problem inspired by Matteo Frigo.)

ord :: Char -> Int

-- returns (f x1) : (f x2) : ... : (f xn) : []
map          :: (a->b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

-- returns (((z f x1) f x2) ... f xn)
foldl            :: (a->b->a) -> a -> [b] -> a
foldl f z []     = z
foldl f z (x:xs) = foldl f (f z x) xs

PLE Home page
Last modified: Sun Feb 4 21:14:05 EST 1996