Haskell Notes

This is a short collection of notes for a tutorial on Haskell presented at group lunch. It follows a presentation by Yuhong Xiong on ML the previous week.

About Haskell

Haskell is a lazy, strongly-typed functional programming language. If you've never used a modern functional language, you might be surprised at some of things it can do.

Instructions

The examples in these notes are contained in Haskell source files, linked from this page. Run the hugs binary, or if you are on Windows, run the winhugs binary -- it is basically the same thing but allows you to browse the type hierarchy. At the command prompt, change to the directory containing the example files. For example 

:cd c:/html/haskell/

The examples are of two kinds. Expressions can be input on the Hugs command line, as in 

Prelude> map (+1) [1, 2, 3]

Function definitions must be loaded from a file. For example, 

Prelude> :load examples
will load the example file example.hs.

Types

Haskell has a comprehensive set of types. Some examples (type the value to the left of the command line to verify that the interpreter infers the correct type): 

7        :: Int
3.1415   :: Float
True     :: Bool
'z'      :: Char
Load the Complex module (with :load Complex) and try 
1 :+ 2.7 :: Complex Double

(More about types later.)

Functions

Functions are defined polymorphically over type classes. Here's a familiar example: 

fact n = if n == 0 then 1 else n * fact (n-1)
To execute this, type eg fact 4 on the command line. Note that no type was given for this function. To see the type inferred by Haskell, simply type fact on the command line -- you will see that this is a function from Int to Int.

There are other features of Haskell that provide more powerful ways of defining functions. This version uses guards: 

factg n | n == 0    = 1
        | otherwise = n * fact (n - 1)
This version uses pattern-matching: 
factp 0 = 1
factp n = n * factp (n - 1)

Patterns

A pattern is formed when a data constructor appears on the left-hand side of a binding. The right-hand side is bound to the corresponding identifiers in the pattern. For example (see the file patt.hs: 
(x:xs) = [1,2,3,4,5]
binds x to 1 and xs to [2,3,4,5]. A lot of useful functions are best defined using patterns: 
map1 f []     = []
map1 f (x:xs) = f x : map1 f xs
For example, evaluate map (+1) [1,2,3,4,5]. To see the type of map, just type its name at the command prompt.

Patterns can also be defined using wild-cards. Here is a more common way of defining map: 

map2 f (x:xs) = f x : map2 f xs
map2 _ _      = []

Higher-order functions and currying

Haskell is implicitly higher-order, meaning that funtions can be accepted as arguments and returned as arguments. The definitions of map above fill this example. In addition, it is curried, meaning that it takes one argument at a time.

For example, consider the mpy 

mpy :: Num a => a -> a -> a
mpy x y = x * y
Obviously, this multiplies two numbers together. Because of currying, however, the arguments can be supplied one at a time. So, 
double :: Num a => a -> a
double = mpy 2
defines the function that multiplies any other number by 2.. Try it with say double 3. Note that we have supplied type signatures here -- without them, Haskell will infer that mpy is a function on Ints, which is more restrictive than we really want.

More on types

We can define new data types and functions on them: 
data CodeRating = Red | Yellow | Green | Blue
                  deriving (Show, Eq)

instance Ord CodeRating where
    compare a b = compare (cix a) (cix b)

cix :: CodeRating -> Int
cix Red = 0
cix Yellow = 1
cix Green = 2
cix Blue = 3

Infinitum

Haskell is lazy, which means that it evaluates expressions only when their values are needed. Full laziness is quite a subtle thing, and is not at all what many people assume it to be. (So be careful when you use the term "lazy evaluation"!). One thing you can do is define an infinite sequence: 
ones = 1 : ones
To see the value, use something like 
take 20 ones
which takes the first 20 elements from the infinite stream. Here's a function that generate an infinite "ramp": 
ramp value step = value : ramp (value+step) step
We can easily generate more complex infinite sequences using recursion: 
square n = take n (repeat 1.0) ++ take n (repeat (-1.0)) ++ square n
impulse = 1.0 : repeat 0.0
In signal processing, we often want to "buffer" a signal into overlapping segments. This function models that: 
chop n []       = []
chop n xs = take n xs : chop n (tail xs)
Now we can define an FIR filter function. The first argument is the coefficient vector (backwards), while the second is the infinite stream to be filtered. 
fir hs xs = map (ip hs) (chop n (take (n-1) (repeat 0.0) ++ xs)) where
    ip as bs = sum (zipWith (*) as bs)
    n = length hs
Try, for example: 
take 20 (fir [0.1, 0.9, 1.0, 0.9, 0.1] impulse)
and 
take 20 (fir [0.1, 0.9, 1.0, 0.9, 0.1] (square 5))