h$4*3      Safe-Inferred>3search-algorithmsbfs 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  . Returns  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 67Just [25,50,60,65,66,67]search-algorithmsdfs next found initial performs a depth-first search over a set of states, starting with initial) and generating neighboring states with next5. It returns a depth-first path to a state for which found returns  . Returns  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]search-algorithms 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  . Returns + 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 dollarscountChange target = dijkstra (add_coin `pruning` (> target)) true_cost (== target) 0 where8 coin_values = [(25, 25), (10, 1000), (5, 5), (1, 1)]2 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 67Just (67,[1,2,7,12,17,42,67])search-algorithms 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  . Returns + if no path to a solved state is possible.search-algorithms'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 . 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 * 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)]6dist (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)])search-algorithms'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 . 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 * if no path to a solved state is possible.search-algorithmsbfsM is a monadic version of : it has support for monadic next and found parameters.search-algorithmsdfsM is a monadic version of : it has support for monadic next and found parameters.search-algorithms dijkstraM is a monadic version of : it has support for monadic next, cost, and found parameters. search-algorithmsaStarM is a monadic version of : it has support for monadic next, cost,  remaining, and found parameters. search-algorithmsincrementalCosts 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 path5 returned by one of these searches, you want to use )incrementalCosts cost_fn (initial : path).0Example: Getting incremental costs from dijkstraimport Data.Maybe (fromJust):{ 1cyclicWeightedGraph :: 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) Set.fromList [0..x]) `pruning` even) 10 [1,3,5,7,9]3Example: 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', []) ]:}8dfs ((graph Map.!) `pruning` (`elem` "bd")) (== 'e') 'a' Just "ce" search-algorithmspruningM is a monadic version of  : it has support for monadic next and  predicate parameterssearch-algorithms8Function to generate "next" states given a current statesearch-algorithms*Predicate to determine if solution found.  returns a path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms7First path found to a state matching the predicate, or  if no such path exists.search-algorithmsFunction to generate "next" states given a current state. These should be given in the order in which states should be pushed onto the stack, i.e. the "last" state in the Foldable will be the first one visited.search-algorithms*Predicate to determine if solution found.  returns a path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms7First path found to a state matching the predicate, or  if no such path exists.search-algorithmsFunction to generate list of neighboring states given the current statesearch-algorithmsFunction to generate transition costs between neighboring states. This is only called for adjacent states, so it is safe to have this function be partial for non-neighboring states.search-algorithms*Predicate to determine if solution found.  returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicatesearch-algorithmsfunction to generate list of neighboring states with associated transition costs given the current statesearch-algorithms*Predicate to determine if solution found.  returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicatesearch-algorithmsFunction to generate list of neighboring states given the current statesearch-algorithmsFunction to generate transition costs between neighboring states. This is only called for adjacent states, so it is safe to have this function be partial for non-neighboring states.search-algorithms(Estimate on remaining cost given a statesearch-algorithms*Predicate to determine if solution found.  returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicatesearch-algorithmsfunction to generate list of neighboring states with associated transition costs given the current statesearch-algorithms(Estimate on remaining cost given a statesearch-algorithms*Predicate to determine if solution found.  returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicatesearch-algorithms8Function to generate "next" states given a current statesearch-algorithms*Predicate to determine if solution found.  returns a path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms7First path found to a state matching the predicate, or  if no such path exists.search-algorithms8Function to generate "next" states given a current statesearch-algorithms*Predicate to determine if solution found.  returns a path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms7First path found to a state matching the predicate, or  if no such path exists.search-algorithmsFunction to generate list of neighboring states given the current statesearch-algorithmsFunction to generate list of costs between neighboring states. This is only called for adjacent states, so it is safe to have this function be partial for non-neighboring states.search-algorithms*Predicate to determine if solution found.  returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicate search-algorithmsFunction which, when given the current state, produces a list whose elements are (incremental cost to reach neighboring state, estimate on remaining cost from said state, said state).search-algorithmsFunction to generate list of costs between neighboring states. This is only called for adjacent states, so it is safe to have this function be partial for non-neighboring states.search-algorithms(Estimate on remaining cost given a statesearch-algorithms*Predicate to determine if solution found.   returns the shortest path to the first state for which this predicate returns .search-algorithms Initial statesearch-algorithms(Total cost, list of steps) for the first path found which satisfies the given predicate search-algorithmsFunction to generate list of costs between neighboring states. This is only called for adjacent states in the states list, so it is safe to have this function be partial for non-neighboring states.search-algorithmsA path, given as a list of adjacent states, along which to find the incremental costssearch-algorithms*List of incremental costs along given path search-algorithmsFunction to generate list of costs between neighboring states. This is only called for adjacent states in the states list, so it is safe to have this function be partial for non-neighboring states.search-algorithmsA path, given as a list of adjacent states, along which to find the incremental costssearch-algorithms*List of incremental costs along given path search-algorithms Function to generate next statessearch-algorithmsPredicate to prune onsearch-algorithms Version of next$ which excludes elements satisfying  predicate search-algorithms Function to generate next statessearch-algorithmsPredicate to prune onsearch-algorithms Version of next$ which excludes elements satisfying  predicate       .search-algorithms-0.3.2-5Isq1fMCy2PJ8cNh1Wv3YWAlgorithm.Searchbfsdfsdijkstra dijkstraAssocaStar aStarAssocbfsMdfsM dijkstraMaStarMincrementalCostsincrementalCostsMpruningpruningM$fSearchContainerLIFOHeap$fSearchContainer[]$fSearchContainerSeqghc-prim GHC.TypesTruebase GHC.MaybeNothing