Week 12: Notes

Our topics this week included

• modules

• exhaustive search

• graph representations

• depth-first search

• breadth-first search

• searching in state spaces

You can read about modules in chapter 7 of Learn You A Haskell.

exhaustive search

Here's the N-queens solution we discussed in the lecture:

no_attack :: Int -> Int -> Int -> Bool
no_attack y1 y2 dx = y1 /= y2 && abs (y1 - y2) /= dx

no_attack_any :: Int -> [Int] -> Bool
no_attack_any y ys = and (zipWith (no_attack y) ys [1 ..])

-- Given a board size N, return all possible ways to place N queens on the board.
queens :: Int -> [[Int]]
queens size =
    let solve 0 = [[]]
        solve n = [y : ys | ys <- solve (n - 1), y <- [1 .. size], no_attack_any y ys]
    in solve size

graph representations

Here's a adjacency-list representation for graphs in Haskell:

type Graph a = [(a, [a])]

adjacent :: Eq a => Graph a -> a -> [a]
adjacent graph v = fromJust (lookup v graph)

sample graph

Here's the sample graph that we used for testing our graph algorithms:

graph1 :: Graph Int
graph1 =
    [(0, [1, 5]), (1, []), (2, [0, 3]), (3, [2, 5]), (4, [2, 3]),
     (5, [4]), (6, [0, 8, 9]), (7, [6, 9]), (8, [6]), (9, [10, 11]),
     (10, [12]), (11, [4, 12]), (12, [9])]

depth-first search with an implicit stack

-- Return a list of visited vertices in the order they were visited.
dfs :: Eq a => Graph a -> a -> [a]
dfs graph start =
    let visit visited v =
            if elem v visited then visited
            else foldl visit (v : visited) (adjacent graph v)
    in reverse (visit [] start)

depth-first search with an explicit stack

As we discussed in the lecture, in a graph search we can avoid cycles in either of two ways:

• We can use a visited set that holds all vertices that have ever been added to the frontier. Before adding any vertex to the frontier, we first check if it's in the visited set. With this approach, no vertex may ever appear twice in the frontier data structure (i.e. in the stack in a depth-first search).

• We can use an explored set that holds all vertices that have been explored. When we pull a vertex from the frontier, we check whether it is already in the explored set; if so, we ignore it. With this approach, a vertex may appear in the frontier more than once.

The approach with an explored set may use more memory in some search spaces. Otherwise the performance of these is likely to be similar, and both these approaches are used in practice. In our course we will use an explored set for graph algorithms since it will often make the code simpler.

-- explicit stack: return list of vertices visited, in order
dfs :: Eq a => Graph a -> a -> [a]
dfs graph start =
    let search explored [] = explored
        search explored (v : stack) =
            if elem v explored then search explored stack
            else search (v : explored) (adjacent graph v ++ stack)
    in reverse $ search [] [start]

breadth-first search with a queue

This function is very similar to the depth-first search function in the previous section.

-- return list of vertices visited, in order
bfs :: Eq a => Graph a -> a -> [a]
bfs graph start =
    let search explored [] = explored
        search explored (v : queue) =
            if elem v explored then search explored queue
            else search (v : explored) (queue ++ adjacent graph v)
    in reverse $ search [] [start]

breadth-first search, returning the shortest path between two vertices

In the function below, the queue holds a list of paths. Each path is a list of vertices from the start vertex to a vertex V, in reverse order.

extend :: Eq a => Graph a -> [a] -> [[a]]
extend graph path@(v : _) = map (: path) (adjacent graph v)

-- return shortest path from start to end vertex
bfs2 :: Eq a => Graph a -> a -> a -> Maybe [a]
bfs2 graph start goal =
    let search explored [] = Nothing
        search explored (path@(v : _) : queue)
            | v == goal = Just path
            | elem v explored = search explored queue
            | otherwise = search (v : explored) (queue ++ extend graph path)
    in reverse <$> search [] [[start]]

searching in a state space

Many problems involve searching in a state space. We can express a state space in Haskell as a pair of functions:

-- s = state type, a = action type
--   possible function: s -> [a]
--   result function: s -> a -> s
type StateSpace s a = (s -> [a], s -> a -> s)

The first function takes a state and returns a list of actions that are possible in that state. The second function takes a state and an action that can be performed in that state, and returns the resulting state.

We can modify our breadth-first search function above so that it can perform a state space search. Given a state space, a start state, and a function that indicates whether a state is a goal state, it finds the shortest path from the start state to any goal state. In this function, each queue element is a pair of type ([a], s), i.e. a state plus a list of actions that lead from the start state to that state.

extend_path :: StateSpace s a -> ([a], s) -> [([a], s)]
extend_path (possible, result) (actions, state) =
    [(a : actions, result state a) | a <- possible state ]

-- return shortest path from start state to goal state
solve :: Eq s => StateSpace s a -> s -> (s -> Bool) -> Maybe [a]
solve space start isGoal =
    let search explored [] = Nothing
        search explored ((actions, state) : queue)
            | isGoal state = Just actions
            | elem state explored = search explored queue
            | otherwise = search (state : explored) (queue ++ extend_path space (actions, state))
    in reverse <$> search [] [([], start)]