Haskell Treasure

This is our yield from the Haskell treasure hunt.

Special forms

Haskell has no mutation of bindings (or data structures, i.e. set-car!).
Haskell knows the type of everything at compile-time. (Caveat: contravariance, as discussed in the Sather Treasure.)
begin is used in Scheme to evaluate statements for side-effect. Haskell has no side-effects. (However, Haskell 1.3 does have a do form, used for sequentialization.)
Lazy evaluation is the default in Haskell. Haskell does however have the opposite of delay, called
if does not need to be a special form in Haskell, because of lazy evaluation.

Here is one attempt, using the declarative style:

flatten :: [[a]] -> [a]
flatten [[]] = []
flatten ([]:ys) = flatten ys
flatten ((x:xs):ys) = x : (flatten (xs:ys))

However, the last two lines are just the append operator ++:

flatten :: [[a]] -> [a]
flatten [] = []
flatten (y:ys) = y ++ (flatten ys)

But this is just a fold:

flatten :: [[a]] -> [a]
flatten = foldl (++) []

Higher-order functions have allowed us to shorten the code. Whether or not it is clearer is up to you.

Alas, we cannot implement superflatten, because it must have only one type. Lists of different depths have different types:

[1, 2] :: [Int]
[[1,2], [3,4]] :: [[Int]]
[[[1,2],[3,4]], [[5,6],[7,8]]] :: [[[Int]]]

And these types cannot be unified by a type-variable.

However, we can implement superflatten, aka fringe, on binary trees. See the Haskell tutorial.

List comprehensions are handy, as demonstrated here, but they are just sugar. See SICP for a desugaring, called "collect".

Array comprehensions, however, are much more important. Otherwise we would have to use the inefficient incremental-update operators.

hash :: [Char] -> Int
hash = (foldl (+) 0) . (map ord)

hash "MSDOS 6.000"    -- prints 666
hash "SYSTEM 7.0"     -- prints 666

Coincidence? We think not.

Last modified: Thu Jan 25 14:18:44 EST 1996