bfs next found initial performs a breadth-first search over a set of states, starting with initial, and generating neighboring states with next. It returns a path to a state for which found returns True. Returns Nothing if no path is possible.

Example: Making change problem

>>> :{
countChange target = bfs (add_one_coin `pruning` (> target)) (== target) 0
  where
    add_one_coin amt = map (+ amt) coins
    coins = [25, 10, 5, 1]
:}

>>> countChange 67
Just [25,50,60,65,66,67]

dfs next found initial performs a depth-first search over a set of states, starting with initial and generating neighboring states with next. It returns a depth-first path to a state for which found returns True. Returns Nothing if no path is possible.

Example: Simple directed graph search

>>> import qualified Data.Map as Map

>>> graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]

>>> dfs (graph Map.!) (== 4) 1
Just [3,4]

dijkstra next cost found initial performs a shortest-path search over a set of states using Dijkstra's algorithm, starting with initial, generating neighboring states with next, and their incremental costs with costs. This will find the least-costly path from an initial state to a state for which found returns True. Returns Nothing if no path to a solved state is possible.

Example: Making change problem, with a twist

>>> :{
-- Twist: dimes have a face value of 10 cents, but are actually rare
-- misprints which are worth 10 dollars
countChange target =
  dijkstra (add_coin `pruning` (> target)) true_cost  (== target) 0
  where
    coin_values = [(25, 25), (10, 1000), (5, 5), (1, 1)]
    add_coin amt = map ((+ amt) . snd) coin_values
    true_cost low high =
      case lookup (high - low) coin_values of
        Just val -> val
        Nothing -> error $ "invalid costs: " ++ show high ++ ", " ++ show low
:}

>>> countChange 67
Just (67,[1,2,7,12,17,42,67])

dijkstraAssoc next found initial performs a shortest-path search over a set of states using Dijkstra's algorithm, starting with initial, generating neighboring states with associated incremenal costs with next. This will find the least-costly path from an initial state to a state for which found returns True. Returns Nothing if no path to a solved state is possible.

aStar next cost remaining found initial performs a best-first search using the A* search algorithm, starting with the state initial, generating neighboring states with next, their cost with cost, and an estimate of the remaining cost with remaining. This returns a path to a state for which found returns True. If remaining is strictly a lower bound on the remaining cost to reach a solved state, then the returned path is the shortest path. Returns Nothing if no path to a solved state is possible.

Example: Path finding in taxicab geometry

>>> :{
neighbors (x, y) = [(x, y + 1), (x - 1, y), (x + 1, y), (x, y - 1)]
dist (x1, y1) (x2, y2) = abs (y2 - y1) + abs (x2 - x1)
start = (0, 0)
end = (0, 2)
isWall = (== (0, 1))
:}

>>> aStar (neighbors `pruning` isWall) dist (dist end) (== end) start
Just (4,[(1,0),(1,1),(1,2),(0,2)])

aStarAssoc next remaining found initial performs a best-first search using the A* search algorithm, starting with the state initial, generating neighboring states and their associated costs with next, and an estimate of the remaining cost with remaining. This returns a path to a state for which found returns True. If remaining is strictly a lower bound on the remaining cost to reach a solved state, then the returned path is the shortest path. Returns Nothing if no path to a solved state is possible.

bfsM is a monadic version of bfs: it has support for monadic next and found parameters.

dfsM is a monadic version of dfs: it has support for monadic next and found parameters.

dijkstraM is a monadic version of dijkstra: it has support for monadic next, cost, and found parameters.

aStarM is a monadic version of aStar: it has support for monadic next, cost, remaining, and found parameters.

incrementalCosts cost_fn states gives a list of the incremental costs going from state to state along the path given in states, using the cost function given by cost_fn. Note that the paths returned by the searches in this module do not include the initial state, so if you want the incremental costs along a path returned by one of these searches, you want to use incrementalCosts cost_fn (initial : path).

Example: Getting incremental costs from dijkstra

>>> import Data.Maybe (fromJust)

>>> :{
cyclicWeightedGraph :: Map.Map Char [(Char, Int)]
cyclicWeightedGraph = Map.fromList [
  ('a', [('b', 1), ('c', 2)]),
  ('b', [('a', 1), ('c', 2), ('d', 5)]),
  ('c', [('a', 1), ('d', 2)]),
  ('d', [])
  ]
start = (0, 0)
end = (0, 2)
cost a b = fromJust . lookup b $ cyclicWeightedGraph Map.! a
:}

>>> incrementalCosts cost ['a', 'b', 'd']
[1,5]

incrementalCostsM is a monadic version of incrementalCosts: it has support for a monadic const_fn parameter.

next `pruning` predicate streams the elements generate by next into a list, removing elements which satisfy predicate. This is useful for the common case when you want to logically separate your search's next function from some way of determining when you've reached a dead end.

Example: Pruning a Set

>>> import qualified Data.Set as Set

>>> ((\x -> Set.fromList [0..x]) `pruning` even) 10
[1,3,5,7,9]

Example: depth-first search, avoiding certain nodes

>>> import qualified Data.Map as Map

>>> :{
graph = Map.fromList [
  ('a', ['b', 'c', 'd']),
  ('b', [undefined]),
  ('c', ['e']),
  ('d', [undefined]),
  ('e', [])
  ]
:}

>>> dfs ((graph Map.!) `pruning` (`elem` "bd")) (== 'e') 'a'
Just "ce"

pruningM is a monadic version of pruning: it has support for monadic next and predicate parameters