-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Common graph search algorithms
--   
--   Library containing common graph search algorithms, including
--   depth-first and breadth-first searches, Dijkstra's algorithm, and A*
@package search-algorithms
@version 0.3.0


-- | This module contains a collection of generalized graph search
--   algorithms, for when you don't want to explicitly represent your data
--   as a graph. The general idea is to provide these algorithms with a way
--   of generating "next" states, a way of generating associated
--   information, a way of determining when you have found a solution, and
--   an initial state.
module Algorithm.Search

-- | <tt>bfs next found initial</tt> performs a breadth-first search over a
--   set of states, starting with <tt>initial</tt>, and generating
--   neighboring states with <tt>next</tt>. It returns a path to a state
--   for which <tt>found</tt> returns <a>True</a>. Returns <a>Nothing</a>
--   if no path is possible.
--   
--   <h3>Example: Making change problem</h3>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   countChange target = bfs (add_one_coin `pruning` (&gt; target)) (== target) 0
--     where
--       add_one_coin amt = map (+ amt) coins
--       coins = [25, 10, 5, 1]
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; countChange 67
--   Just [25,50,60,65,66,67]
--   </pre>
bfs :: (Foldable f, Ord state) => (state -> f state) -> (state -> Bool) -> state -> Maybe [state]

-- | <tt>dfs next found initial</tt> performs a depth-first search over a
--   set of states, starting with <tt>initial</tt> and generating
--   neighboring states with <tt>next</tt>. It returns a depth-first path
--   to a state for which <tt>found</tt> returns <a>True</a>. Returns
--   <a>Nothing</a> if no path is possible.
--   
--   <h3>Example: Simple directed graph search</h3>
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.Map as Map
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; dfs (graph Map.!) (== 4) 1
--   Just [3,4]
--   </pre>
dfs :: (Foldable f, Ord state) => (state -> f state) -> (state -> Bool) -> state -> Maybe [state]

-- | <tt>dijkstra next cost found initial</tt> performs a shortest-path
--   search over a set of states using Dijkstra's algorithm, starting with
--   <tt>initial</tt>, generating neighboring states with <tt>next</tt>,
--   and their incremental costs with <tt>costs</tt>. This will find the
--   least-costly path from an initial state to a state for which
--   <tt>found</tt> returns <a>True</a>. Returns <a>Nothing</a> if no path
--   to a solved state is possible.
--   
--   <h3>Example: Making change problem, with a twist</h3>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   -- 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` (&gt; 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 -&gt; val
--           Nothing -&gt; error $ "invalid costs: " ++ show high ++ ", " ++ show low
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; countChange 67
--   Just (67,[1,2,7,12,17,42,67])
--   </pre>
dijkstra :: (Foldable f, Num cost, Ord cost, Ord state) => (state -> f state) -> (state -> state -> cost) -> (state -> Bool) -> state -> Maybe (cost, [state])

-- | <tt>aStar next cost remaining found initial</tt> performs a best-first
--   search using the A* search algorithm, starting with the state
--   <tt>initial</tt>, generating neighboring states with <tt>next</tt>,
--   their cost with <tt>cost</tt>, and an estimate of the remaining cost
--   with <tt>remaining</tt>. This returns a path to a state for which
--   <tt>found</tt> returns <a>True</a>. If <tt>remaining</tt> is strictly
--   a lower bound on the remaining cost to reach a solved state, then the
--   returned path is the shortest path. Returns <a>Nothing</a> if no path
--   to a solved state is possible.
--   
--   <h3>Example: Path finding in taxicab geometry</h3>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   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))
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; aStar (neighbors `pruning` isWall) dist (dist end) (== end) start
--   Just (4,[(1,0),(1,1),(1,2),(0,2)])
--   </pre>
aStar :: (Foldable f, Num cost, Ord cost, Ord state) => (state -> f state) -> (state -> state -> cost) -> (state -> cost) -> (state -> Bool) -> state -> Maybe (cost, [state])

-- | <tt>bfsM</tt> is a monadic version of <a>bfs</a>: it has support for
--   monadic <tt>next</tt> and <tt>found</tt> parameters.
bfsM :: (Monad m, Foldable f, Ord state) => (state -> m (f state)) -> (state -> m Bool) -> state -> m (Maybe [state])

-- | <tt>dfsM</tt> is a monadic version of <a>dfs</a>: it has support for
--   monadic <tt>next</tt> and <tt>found</tt> parameters.
dfsM :: (Monad m, Foldable f, Ord state) => (state -> m (f state)) -> (state -> m Bool) -> state -> m (Maybe [state])

-- | <tt>dijkstraM</tt> is a monadic version of <a>dijkstra</a>: it has
--   support for monadic <tt>next</tt>, <tt>cost</tt>, and <tt>found</tt>
--   parameters.
dijkstraM :: (Monad m, Foldable f, Num cost, Ord cost, Ord state) => (state -> m (f state)) -> (state -> state -> m cost) -> (state -> m Bool) -> state -> m (Maybe (cost, [state]))

-- | <tt>aStarM</tt> is a monadic version of <a>aStar</a>: it has support
--   for monadic <tt>next</tt>, <tt>cost</tt>, <tt>remaining</tt>, and
--   <tt>found</tt> parameters.
aStarM :: (Monad m, Foldable f, Num cost, Ord cost, Ord state) => (state -> m (f state)) -> (state -> state -> m cost) -> (state -> m cost) -> (state -> m Bool) -> state -> m (Maybe (cost, [state]))

-- | <tt>incrementalCosts cost_fn states</tt> gives a list of the
--   incremental costs going from state to state along the path given in
--   <tt>states</tt>, using the cost function given by <tt>cost_fn</tt>.
--   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 <tt>path</tt> returned by one of these searches, you want to use
--   <tt>incrementalCosts cost_fn (initial : path)</tt>.
--   
--   <h3>Example: Getting incremental costs from dijkstra</h3>
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Maybe (fromJust)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   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
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; incrementalCosts cost ['a', 'b', 'd']
--   [1,5]
--   </pre>
incrementalCosts :: (state -> state -> cost) -> [state] -> [cost]

-- | <tt>incrementalCostsM</tt> is a monadic version of
--   <a>incrementalCosts</a>: it has support for a monadic
--   <tt>const_fn</tt> parameter.
incrementalCostsM :: (Monad m) => (state -> state -> m cost) -> [state] -> m [cost]

-- | <tt>next `pruning` predicate</tt> streams the elements generate by
--   <tt>next</tt> into a list, removing elements which satisfy
--   <tt>predicate</tt>. This is useful for the common case when you want
--   to logically separate your search's <tt>next</tt> function from some
--   way of determining when you've reached a dead end.
--   
--   <h3>Example: Pruning a Set</h3>
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.Set as Set
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; ((\x -&gt; Set.fromList [0..x]) `pruning` even) 10
--   [1,3,5,7,9]
--   </pre>
--   
--   <h3>Example: depth-first search, avoiding certain nodes</h3>
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Data.Map as Map
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; :{
--   graph = Map.fromList [
--     ('a', ['b', 'c', 'd']),
--     ('b', [undefined]),
--     ('c', ['e']),
--     ('d', [undefined]),
--     ('e', [])
--     ]
--   :}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; dfs ((graph Map.!) `pruning` (`elem` "bd")) (== 'e') 'a'
--   Just "ce"
--   </pre>
pruning :: (Foldable f) => (a -> f a) -> (a -> Bool) -> (a -> [a])

-- | <tt>pruningM</tt> is a monadic version of <a>pruning</a>: it has
--   support for monadic <tt>next</tt> and <tt>predicate</tt> parameters
pruningM :: (Monad m, Foldable f) => (a -> m (f a)) -> (a -> m Bool) -> (a -> m [a])
instance Algorithm.Search.SearchContainer (Data.Sequence.Internal.Seq a)
instance Algorithm.Search.SearchContainer [a]
instance GHC.Classes.Ord k => Algorithm.Search.SearchContainer (Algorithm.Search.LIFOHeap k a)
