Week 14: Notes

Either
modules
random numbers
monads

You can read about these topics in Learn You a Haskell, chapters 7, 9, 11, and 12.

Note that the System.Random module is included in the random package, which is not included in a default Haskell installation. You can install it using the Cabal package manager:

$ cabal install --lib random

packages

Haskell modules are contained in installable units called packages. The default installation of Haskell includes a number of packages including

base (which contains the fundamental modules Prelude, Data.Int, Data.List and many others)
array (which contains Data.Array)
containers (which contains various collection types such as Data.Set and Data.Map)

and many others.

You can install additional packages using Cabal, a package manager that comes with Haskell. Cabal is somewhat similar to Python's package manager pip: it can download packages from the internet and install them on your system. For example, as mentioned above you can use Cabal to install the random package:

$ cabal install --lib random

The command ghc-pkg list will list packages that are installed on your system. Its output looks like this:

$ ghc-pkg list
/home/adam/.ghcup/ghc/9.2.7/lib/ghc-9.2.7/package.conf.d
    Cabal-3.6.3.0
    array-0.5.4.0
    base-4.16.4.0
    binary-0.8.9.0
    bytestring-0.11.4.0
    containers-0.6.5.1
    deepseq-1.4.6.1
    ...

However this list is not complete: it may not include packages that you installed using Cabal. Those will be listed in a package environment file on your machine. When you run ghci, it prints the path of this file:

$ ghci
Loaded package environment from /home/adam/.ghc/x86_64-linux-9.2.7/environments/default
GHCi, version 9.2.7: https://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /home/adam/Dropbox/ubuntu/ghci
>

On my machine, this package environment file looks like this:

$ cat /home/adam/.ghc/x86_64-linux-9.2.7/environments/default
clear-package-db
global-package-db
package-db /home/adam/.cabal/store/ghc-9.2.7/package.db
package-id ghc-9.2.7
package-id bytestring-0.11.4.0
package-id unix-2.7.2.2
...
package-id directory-1.3.6.2
package-id text-1.2.5.0
package-id random-1.2.1.1-14950f0d57c55eed8fd0701e27e87527c3c7ef42acca95164df8337d2d526ad3
$

Notice the random package at the end of the listing.

dynamic programming

In Haskell list elements (like all other values) are evaluated lazily. They may even refer to other elements of the same list:

> xs = [10, 20, xs !! 0 + xs !! 1]
> xs !! 0
10
> xs !! 2
30

Dependencies between list elements may be in any order:

> xs = [xs !! 2 + 2, 0, xs !! 1 + 10]
> xs !! 0
12

So we can build an entire list using a recursive calculation.

Building on this idea, we can implement dynamic programming in Haskell by defining a function and a list using mutual recursion. The list will hold a cache values computed by the function, so that no value will be computed twice.

For example, consider the following function that calculates the Nth Fibonacci number recursively. It is exponentially inefficient:

fib :: Int -> Int
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

We can use cache each return value in a list:

fib :: Int -> Int
fib n = cache !! n where
  cache = map f [0 ..]
  f 0 = 1
  f 1 = 1
  f n = cache !! (n - 1) + cache !! (n - 2)

Now the function will run much more quickly. However, it will still take O(N²) time to compute the Nth Fibonacci number, since the lookup operator (!!) runs in O(N). To improve this running time we will need to use arrays, the subject of the next section.

Note that each time the function runs it will recompute the cache of Fibonacci values. We can make a slight change to the function to cause the cache to be shared between invocations:

fib :: Int -> Int
fib = (cache !!) where
  cache = map f [0 ..]
  f 0 = 1
  f 1 = 1
  f n = cache !! (n - 1) + cache !! (n - 2)

With this change the 'where' block is not nested inside an invocation of 'fib', so the values that the block computes will be persistent.

arrays

Haskell has immutable arrays that allow you to access elements in O(1) using the ! operator. You'll need to import Data.Array to use these.

The listArray function builds an array given a range of indices and a list of values. Let's build an array whose indices are the values 0..5:

> a = listArray (0, 5) [2, 9, 8, 3, 7, 6]

Now we can access elements in constant time:

> a ! 2
8
> a ! 4
7

Array indices can be any instance of the Ix type class. That includes Int, Integer, Char, and also tuples of types belonging to Ix. So we can construct, for example, a 2-dimensional array whose indices are of type (Int, Int):

> a = listArray ((0, 0), (2, 2)) [7, 2, 4, 8, 9, 5, 3, 11, 14]

This represents the matrix

1  2  4
8  9  5
3  11 14

Again, we can access elements in constant time:

> a ! (1, 1)
9
> a ! (1, 2)
5

dynamic programming using an array

Let's revisit the function we saw above that computes the Nth Fibonacci number using dynamic programming:

fib :: Int -> Int
fib n = cache !! n where
  cache = map f [0 ..]
  f 0 = 1
  f 1 = 1
  f n = cache !! (n - 1) + cache !! (n - 2)

We can make the function more efficient using an array: