úÎaj`*Safe9;<=? The 8 class abstracts the idea of a container to be used in  A  ú 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 prunes found initialF performs a breadth-first search over a set of states, starting with initial&, generating neighboring states with next4, and pruning out any state for which a function in prunes returns  ). 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 [(> 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 prunes found initialD performs a depth-first search over a set of states, starting with initial&, generating neighboring states with next4, and pruning out any state for which a function in prunes returns  5. 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 prunes found initiala performs a shortest-path search over a set of states using Dijkstra's algorithm, starting with initialB, generating neighboring states and their incremental costs with next5, and pruning out any state for which a function in prunes returns  T. 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 dollarsEcountChange target = dijkstra add_one_coin [(> target)] (== target) 0 where add_one_coin amt =K map (\(true_val, face_val) -> (true_val, face_val + amt)) coin_values8 coin_values = [(25, 25), (1000, 10), (5, 5), (1, 1)]:}countChange 67;Just (67,[(1,1),(1,2),(5,7),(5,12),(5,17),(25,42),(25,67)])aStar next prunes found initialV performs a best-first search using the A* search algorithm, starting with the state initialZ, generating neighboring states, their cost, and an estimate of the remaining cost with next4, and pruning out any state for which a function in prunes returns  +. This returns a path to a state for which found returns  “. If the estimate 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)FnextTowards dest pos = map (\p -> (1, dist p dest, p)) (neighbors pos):};aStar (nextTowards (0, 2)) [(== (0, 1))] (== (0, 2)) (0, 0)2Just (4,[(1,(1,0)),(1,(1,1)),(1,(1,2)),(1,(0,2))])   moves from one  searchState1 to the next in the generalized search algorithmÿNWorkhorse 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 Nothing 8Function to generate "next" states given a current state=List of ways to prune search. These are predicates which, if  +, are considered to indicate a "dead end".*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=List of ways to prune search. These are predicates which, if  +, are considered to indicate a "dead end".*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.]Function to generate list of incremental cost and neighboring states given the current state=List of ways to prune search. These are predicates which, if  +, are considered to indicate a "dead end".*Predicate to determine if solution found. P returns the shortest path to the first state for which this predicate returns  . Initial state¹Function 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).=List of ways to prune search. These are predicates which, if  +, are considered to indicate a "dead end".*Predicate to determine if solution found. P returns the shortest path to the first state for which this predicate returns  . Initial state Empty Function 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=List of ways to prune search. These are predicates which, if  +, are considered to indicate a "dead end".*Predicate to determine if solution found. searchE 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.1.0-B9mxO5R8Ds21tevMr2L6zhAlgorithm.SearchbfsdfsdijkstraaStar$fSearchContainerLIFOHeap(,)$fSearchContainer[]a$fSearchContainerSeqaSearchContainergeneralizedSearch SearchStateghc-prim GHC.TypesTruebaseGHC.BaseNothingnextSearchState findIteratepoppushLIFOHeapcurrentqueuevisitedpaths emptyLIFOHeap