Week 10: Notes

Our Haskell topics this week were

• recursive value definitions

• records

• instance declarations

• kinds

You can read about records, instance declarations, and kinds in chapter 8 "Making Our Own Types and Typeclasses" of the Learn You a Haskell textbook.

recursive value definitions

In our earliest weeks of studying Haskell we saw that a range of integers (or another enumerable type) can be unbounded at one end, which forms an infinite list. For example, [1 ..] is an infinite list of all positive integers.

Let's look at how we can define our own infinite lists without using the range operator. One approach is to use a recursive function:

ints :: [Int]

ints = f 1
  where f a = a : f (a + 1)

> take 10 ints
[1,2,3,4,5,6,7,8,9,10]

Notice that our recursive function f has no base case. In most languages, a recursive function with no base case will cause a program to hang, since it can never terminate. But due to Haskell's lazy evaluation, such a function causes no problem in Haskell.

Alternatively, we may define the infinite list [1, 2, 3, ... ] as a recursively defined value. In other words, we may define the list in terms of itself. Suppose that ints is the list [1, 2, 3, ...]. Notice that if we add 1 to every element in ints, we get [2, 3, ...], which is the tail of ints. In other words, we have observed that

ints == 1 : [i + 1 | i <- ints ]

In Haskell, we may define ints using this equation! In other words, we can write

ints = 1 : [i + 1 | i <- ints ]

and now ints is just the same as before:

> take 10 ints
[1,2,3,4,5,6,7,8,9,10]

Even more compactly, we can define ints as

ints = 1 : map (+1) ints

Let's look at another example. Recall the Fibonacci series:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

We'd like to define an infinite list of all Fibonacci numbers. As before, one way is to use a recursive function:

fibs = f 1 1
    where f a b = a : f b (a + b)

It works:

> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

Alternately, as before we can directly define the sequence recursively. Once more we must find a recursive pattern. Suppose that

fibs             == [1, 1, 2, 3,  5,  8, 13, 21, ...]

Then

tail fibs        == [1, 2, 3, 5,  8, 13, 21, 34, ...]

and

tail (tail fibs) == [2, 3, 5, 8, 13, 21, 34, 55, ...]

Notice above that if we add fibs and (tail fibs) element by element, we get tail (tail fibs). That makes sense, because for n >= 3 we have

F_n = F_{n - 1} + F_{n - 2}

so we can generate each element as the sum of the elements that are one and two positions earlier.

We can use this pattern to define fibs recursively. The zipWith function combines elements of two lists using an arbitrary function, so we can use it to add lists element by element. For example:

> zipWith (+) [1, 2, 3] [100, 150, 200]
[101,152,203]

And so we can define

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The sequence is the same as before:

> take 10 fibs
[1,1,2,3,5,8,13,21,34,55]

It may seem surprising that this is possible at all. But due to Haskell's lazy evaluation this works fine.

fraction type

Here is the Frac type we saw in the lecture:

data Frac = Frac Int Int  -- numerator, denominator

instance Eq Frac where
    (==) (Frac a b) (Frac c d) = (a * d == b * c)

instance Ord Frac where
    compare (Frac a b) (Frac c d) = compare (a * d) (b * c)

Here's a generalized version, in which the numerator and denominator may be of any integral type (i.e. either Int or Integer):

-- a is any Integral type
data GFrac a = GFrac a a

instance (Num a, Eq a) => Eq (GFrac a) where
    (==) (GFrac a b) (GFrac c d) = (a * d == b * c)

instance (Num a, Ord a) => Ord (GFrac a) where
    compare (GFrac a b) (GFrac c d) = compare (a * d) (b * c)

tutorial exercises

iterate

Write the built-in function iterate, which produces an infinite list by repeated applying a function to a value.

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

-- x, f x, f f x, f f f x, .....
iterate' :: (a -> a) -> a -> [a]
iterate' f x =
    let list = x : map f list
    in list

infinite diagonal matrix

Construct an infinite diagonal matrix as an infinite list of lists.

infinite_diag :: [[Int]]
infinite_diag = iterate' (0:) (1 : repeat 0)

Pascal's triangle

Construct Pascal's triangle as an infinite list of lists.

-- transform one row of Pascal's triangle to the next
nextRow :: [Int] -> [Int]
nextRow list =
    [a + b | (a, b) <- zip (0 : list) (list ++ [0]) ]

pascal :: [[Int]]
pascal = iterate' nextRow [1]

Time

Create a Haskell type Time that represents a time of day with 1-second resolution, such as 5:15:02 or 13:12:45.

data Time = Time { hours :: Int, minutes :: Int, seconds :: Int }
  deriving (Eq, Ord)

instance Enum Time where
    toEnum i = Time (i `div` 3600 `mod` 24) (i `div` 60 `mod` 60)
                    (i `mod` 60)
    fromEnum (Time h m s) = s + (m + h * 60) * 60

instance Bounded Time where
    minBound = Time 0 0 0
    maxBound = Time 23 59 59

instance Show Time where
    show (Time h m s) = show h ++ ":" ++ show m ++ ":" ++ show s

makeTime :: Int -> Int -> Int -> Time
makeTime = Time