content: module AI.Search.Uninformed where
  
  import AI.Search.Core
  import AI.Util.Queue
  
  ----------------------------------
  -- Uninformed Search Algorithms --
  ----------------------------------
  
  -- |Search the deepest nodes in the search tree first.
  depthFirstTreeSearch :: (Problem p s a) => p s a -> Maybe (Node s a)
  depthFirstTreeSearch = treeSearch []
  
  -- |Search the shallowest nodes in the search tree first.
  breadthFirstTreeSearch :: (Problem p s a) => p s a -> Maybe (Node s a)
  breadthFirstTreeSearch = treeSearch (newQueue :: FifoQueue (Node s a))
  
  -- |Search the deepest nodes in the graph first.
  depthFirstGraphSearch :: (Problem p s a, Ord s) => p s a -> Maybe (Node s a)
  depthFirstGraphSearch = graphSearch []
  
  -- |Search the shallowest nodes in the graph first.
  breadthFirstGraphSearch :: (Problem p s a, Ord s) => p s a -> Maybe (Node s a)
  breadthFirstGraphSearch = graphSearch (newQueue :: FifoQueue (Node s a))
  
  -- |Return type for depth-limited search. We need this as there are two types of
  --  failure - either we establish that the problem has no solutions ('Fail') or
  --  we can't find any solutions within the depth limit ('Cutoff').
  data DepthLimited a = Fail | Cutoff | Ok a deriving (Show)
  
  -- |Depth-first search with a depth limit. If the depth limit is reached we
  --  return 'Cutoff', otherwise return 'Fail' (if no solution is found) or 'Ok'
  --  (if a solution is found) which take the place of Nothing and Just in the
  --  other search functions.
  depthLimitedSearch :: (Problem p s a) =>
                        Int       -- ^ Depth limit
                     -> p s a     -- ^ Problem
                     -> DepthLimited (Node s a)
  depthLimitedSearch lim prob = recursiveDLS (root prob) prob lim
      where
          recursiveDLS node p lim
              | goalTest p (state node) = Ok node
              | depth node == lim       = Cutoff
              | otherwise               = filt False $ map go (expand prob node)
              where
                  go node = recursiveDLS node p lim
  
                  filt cutoff [] = if cutoff then Cutoff else Fail
                  filt cutoff (Ok node : _)    = Ok node
                  filt cutoff (Fail    : rest) = filt cutoff rest
                  filt cutoff (Cutoff  : rest) = filt True   rest
  
  -- |Repeatedly try depth-limited search with an increasing depth limit.
  iterativeDeepeningSearch :: (Problem p s a) => p s a -> Maybe (Node s a)
  iterativeDeepeningSearch prob = go 1
      where
          go lim = case depthLimitedSearch lim prob of
              Cutoff -> go (lim + 1)
              Fail   -> Nothing
              Ok n   -> Just n