Safe9;<=DR The SearchContainer8 class abstracts the idea of a container to be used in generalizedSearch A  SearchState represents the state of a generalized search at a given point in an algorithms execution. The advantage of this abstraction is that it can be used for things like bidirectional searches, where you want to stop and start a search part-way through.bfs next found initialF 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:{JcountChange 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]dfs next found initialD 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] dijkstra next cost found initiala 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 costsS. 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:{ D-- Twist: dimes have a face value of 10 cents, but are actually rare'-- misprints which are worth 10 dollarscountChange target =C 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 -> valM Nothing -> error $ "invalid costs: " ++ show high ++ ", " ++ show low:}countChange 67Just (67,[1,2,7,12,17,42,67])'aStar next cost remaining found initialV 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:{Cneighbors (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)):}AaStar (neighbors `pruning` isWall) dist (dist end) (== end) start"Just (4,[(1,0),(1,1),(1,2),(0,2)])incrementalCosts cost_fn statesZ 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)<cost a b = fromJust . lookup b $ cyclicWeightedGraph Map.! a:}%incrementalCosts cost ['a', 'b', 'd'][1,5]next `pruning` predicate" streams the elements generate by next/ into a list, removing elements which satisfy  predicateX. This is useful for the common case when you want to logically separate your search's nextG 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]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" nextSearchState moves from one  searchState1 to the next in the generalized search algorithmNWorkhorse simple search algorithm, generalized over search container and path-choosing function. The idea here is that many search algorithms are at their core the same, with these details substituted. By writing these searches in terms of this function, we reduce the chances of errors sneaking into each separate implementation.findIterate found next initial* takes an initial seed value and applies next to it until either found returns True or next returns NothingleastCostly paths_a paths_b( is a utility function to be used with 2-like functions. It returns True when the cost of paths_a is less than the cost of paths_bJ, where the total costs are the first elements in each tuple in each path  8Function to generate "next" states given a current state*Predicate to determine if solution found. E returns a path to the first state for which this predicate returns  . Initial state7First path found to a state matching the predicate, or   if no such path exists.8Function to generate "next" states given a current state*Predicate to determine if solution found. E returns a path to the first state for which this predicate returns  . Initial state7First path found to a state matching the predicate, or   if no such path exists.GFunction to generate list of neighboring states given the current stateFunction 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.*Predicate to determine if solution found. P returns the shortest path to the first state for which this predicate returns  . Initial stateFunction 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).Function 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.(Estimate on remaining cost given a state*Predicate to determine if solution found. P returns the shortest path to the first state for which this predicate returns  . Initial stateoFunction to generate list of costs between neighboring states. This is only called for adjacent states in the statesR list, so it is safe to have this function be partial for non-neighboring states.VA path, given as a list of adjacent states, along which to find the incremental costs*List of incremental costs along given path Function to generate next statesPredicate to prune on Version of next$ which excludes elements satisfying  predicate Empty SearchContainerFunction to turn a stateo into a key by which states will be compared when determining whether a state has be enqueued and / or visited Function better old new', which when given a choice between an old and a new$ path to a state, returns True when new9 is a "better" path than old and should thus be inserted8Function to generate "next" states given a current state*Predicate to determine if solution found. generalizedSearchE returns a path to the first state for which this predicate returns  . Initial state7First path found to a state matching the predicate, or   if no such path exists.         .search-algorithms-0.2.0-BavM5G8i1NuAQQKvXIVTBcAlgorithm.SearchbfsdfsdijkstraaStarincrementalCostspruning$fSearchContainerLIFOHeap$fSearchContainer[]$fSearchContainerSeqSearchContainer SearchStateghc-prim GHC.TypesTruebaseGHC.BaseNothingnextSearchStategeneralizedSearch findIterate leastCostlyElempoppushLIFOHeapcurrentqueuevisitedpaths emptyLIFOHeap