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
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.
We've already seen that we can write a function to generate an infinite list of numbers:
intsFrom :: Integer -> [Integer] intsFrom x = x : intsFrom (x + 1)
For example:
> take 10 (intsFrom 1) [1,2,3,4,5,6,7,8,9,10]
Alternatively we may produce this list using a recursive value definition. Consider an infinite list of integers starting with 1:
[1, 2, 3, 4, 5, ...]
If we add 1 to each element of the list, we get
[2, 3, 4, 5, …]
which is the same as the tail of the original list. So we may in fact define this list as 1 followed by the result of adding 1 to each element:
ints :: [Integer] ints = 1 : map (+1) ints
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(N2) 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.
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
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:
fib :: Int -> Int fib n = cache ! n where cache = listArray (0, n) (map f [0 ..]) f 0 = 1 f 1 = 1 f n = cache ! (n - 1) + cache ! (n - 2)
In a procedural language, we can read or write the array element at a given index in O(1). Haskell's lists are linked lists, so retrieving or replacing an element at the Nth index of a list will take O(N). Last week we learned that Haskell has immutable arrays. We can retrieve an element of a Haskell array in O(1), but if we want to update a single value we must create a new array, which will take O(N) if the array has N elements.
In some situations we may want a sequence of elements in which we can update the element at a given index more quickly. Let's call this a random-access list. If the size of our sequence is fixed, we may implement a random-access list using a binary tree. We can construct the tree to be balanced, so we will be able to read or update elements in O(log N). As one possibility, each tree node could contain a pair (i, v), where i is an index and v is a value. However that is wasteful: the indices form a continuous range of integers, so we don't actually need to store them all in the tree. Instead, we may build a binary tree in which the internal nodes only contain pointers to children, and all values are stored in leaves. As we descend the tree to look for a value at a particular index, we can decide whether to go left or right at each step based on the index we are seeking.
For example, suppose that our sequence contains 7 elements, namely the characters of the string "sundial". We can store them in a tree that looks like this:
The tree has an asymmetrical shape because 7 is not a power of 2, but that is fine. In the above tree, for any node at the root of a subtree with n elements, the left subtree holds (n div 2) elements and the right subtree holds the remaining elements. For example, at the root node the left subtree has (7 div 2) = 3 elements, and the right subtree has the remaining 4 elements. So if we are looking for an element with an index that is less than 3, we can go left, otherwise right.
As an exercise, you may wish to implement a random-access list using this sort of structure.
Haskell's Data.Sequence
module (in the containers package)
contains a type Seq a which is a more
powerful random-access list. This type allows you to read or update
elements by index in O(log N), concatenate or split sequences in
O(log N), and perform various other operations efficiently as well.
How can we build a purely functional set or dictionary data structure? For a dictionary, first suppose that the keys form a fixed set, and are of a comparable type. Then we can build a balanced binary tree in which each node contains a (key, value) pair. Since the keys are fixed, the tree's shape will not change and it will always be balanced. For a set, if we want to store a dynamically changing subset of values from a known fixed set, we can similarly use a dictionary that maps values in that fixed set to a boolean.
For example, suppose that you are implementing an algorithm on a graph whose vertices are named by strings. Since the graph will not change as the algorithm runs, its vertex names are a fixed set and you could use this approach to store a visited set of vertices, or a map from vertices to integers.
In the general case, when keys may be added dynamically and are not all known at the beginning, you can implement a set or dictionary using a self-balancing binary tree structure such as a red-black or AVL tree.
Haskell's containers
package includes modules Data.Set
and Data.Map
which provide set and map types using balanced binary trees. There
are also modules Data.IntSet
and Data.IntMap
which are more efficient when keys are integers.
Just as in other languages, we may represent a graph in Haskell in either adjacency list or adjacency matrix representation.
We can store an adjacency list as an association list mapping each vertex to a list of neighbors:
type Graph a = [(a, [a])]
If the graph vertices are indexed by integer ID, we can alternatively use an array. Then we can look up a vertex's neighbors in O(1):
type Graph = Array Int [Int]
If we want to use an adjacency matrix representation, probably an array will be the most natural choice:
type Graph = Array (Int, Int) Bool
In this class we will mostly use the association-list representation, since we will be using smaller graphs where efficiency doesn't matter too much. For example, here's an undirected graph and its representation:
my_graph :: Graph Char
my_graph = [ ('a', "ce"), ('b', "de"), ('c', "adf"), ('d', "bcef"),
('e', "bdf"), ('f', "cdeg"), ('g', "f") ]Here's a helper function to find a vertex's neighbors:
neighbors :: Eq a => Graph a -> a -> [a] neighbors graph v = fromJust (lookup v graph)
Here's a function that will find all paths between two vertices in a graph:
paths :: Eq a => Graph a -> a -> a -> [[a]]
paths g v w = f [v] v w
where f vis v w
| v == w = [[v]]
| otherwise =
[ v : path | n <- neighbors g v, notElem n vis,
path <- f (n : vis) n w ]Let's run it on the graph above:
> paths my_graph 'a' 'g' ["acdbefg","acdefg","acdfg","acfg","aebdcfg","aebdfg","aedcfg","aedfg","aefg"]
This function uses a visited set to avoid walking in circles. However, notice that its visited set is local to each path that it explores. It only prevents a path from intersecting itself. This function may run in exponential time even when it finds only a single path between the start and end vertices, because it may explore an exponential number of paths before finding a path to the destination. For example, consider a graph with a start vertex that points to two subgraphs: the first is a complete subgraph with N vertices, and the second is a subgraph containing only the destination vertex. The function may explore all N! paths in the complete subgraph before discovering the path to the destination. (In fact this is worse than exponential, since N! grows faster than kN for any k.)
If we want an efficient depth-first or breadth-first search that runs in (almost) O(V + E), we will need a global visited set that is shared among all branches of the exploration. That's the topic of our next section.
Just as in a procedural language, we may implement a depth-first search either (a) by using recursion to explore the graph, or (b) using a stack data structure.
In either case we will need a visited set. In the functions below, we'll use a list to store the visited set. Of course, if we want our code to run efficiently on larger graphs then a structure such as a Data.Set (a balanced binary tree) would be a better choice for the visited set.
To explore a graph recursively in Haskell, we can write a helper function that takes a visited set and a vertex v to explore. The function will return a new visited set, expanded with all the vertices discovered while exploring v and its neighbors.
The function will work as follows: if v has already been visited, it will return the same visited set, unchanged. Otherwise, it will add v to the visited set, and then fold the same function (itself!) over all of v's neighbors. That will explore each neighbor in turn, and accumulate the expansions of the visited set that occur as the neighbors are explored. Here is the code:
-- Perform a depth-first search of a graph, starting with a given vertex.
-- Return a list of all vertices that were visited, in the order in
-- which they were visited.
dfs :: Eq a => Graph a -> a -> [a]
dfs g v = reverse (f [] v)
where f visited v
| elem v visited = visited
| otherwise = foldl f (v : visited) (neighbors g v)Let's run it on the graph above:
> dfs my_graph 'a' "acdbefg"
Alternatively, we may use a stack, represented using a Haskell list. Our recursive helper function will pop a vertex from the stack. If it's already in the visited set, it will ignore it and recurse. Otherwise, it will add the vertex to the visited set, and also push its neighbors onto the stack. Here's an implementation:
dfs :: Eq a => Graph a -> a -> [a]
dfs g v = f [] [v]
where f visited [] = []
f visited (v : stack)
| elem v visited = f visited stack
| otherwise = v : f (v : visited) (neighbors g v ++ stack)It will return vertices in the same order as the previous function that used a fold:
> dfs my_graph 'a' "acdbefg"
To perform a breadth-first search instead, we only need to make a tiny change. Let's rename the variable 'stack' to be called 'queue', and append neighbors to the list instead of prepending:
bfs :: Eq a => Graph a -> a -> [a]
bfs g v = f [] [v]
where f visited [] = []
f visited (v : queue)
| elem v visited = f visited queue
| otherwise = v : f (v : visited) (queue ++ neighbors g v)Of course, on larger graphs it would be better to use a more efficient queue implementation, such as the functional double-stack queue that we saw a few weeks ago. Furthermore, it would also be better to use a more efficient implementation of the visited set.
As an exercise, you may wish to modify this function so that it returns a list of vertices on the shortest path from the start vertex to a given end vertex. Then each item on the queue will not just be a vertex v; instead it will be a path from the start vertex to v, in reverse order.
We may use a similar function to find shortest paths in any state space, as we did when we solved state space problems in Python or C#. To accomplish that, we can write a function 'neighbors' that returns the neighboring states of any given state.