Generalised search functions

SearchPath.hs

module SearchPath (shortestPath, directedPath) where

import Data.Set (empty, member, insert, Set) 


shortestPath :: (Ord s) => ((s, a) -> [(s, a)]) -> ((s, a) -> Bool) -> (s, a) -> [(s, a)]
shortestPath sucsOf isGoal start = searchFron empty [[start]]

             where searchFron _ [] = []
                   searchFron expl (path : fron) = searchSucs expl fron path (sucsOf (last path))

                   searchSucs expl fron path [] = searchFron expl fron
                   searchSucs expl fron path ((state, action) : sucs)

                            | member state expl = searchSucs expl fron path sucs

                            | otherwise = let path' = path ++ [(state, action)]
                                          in  if   isGoal (state, action) 
                                              then path' 
                                              else searchSucs (insert state expl) (fron ++ [path']) path sucs


directedPath :: (Ord s, Eq a) => ((s, a) -> [(s, a)]) -> ((s, a) -> Bool) -> (s, a) -> [(s, a)]
directedPath sucsOf isGoal start = reverse (solve empty [start])

             where solve expl [] = []
                   solve expl path@(current@(state, _) : _) 
                         | isGoal current = path
                         | otherwise = let results = [res | 
                                                      next@(state', _) <- sucsOf current, 
                                                      let res = solve (insert state' expl) (next : path), 
                                                      res /= [],
                                                      not (member state' expl)] 
                                 in case results of
                                         [] -> []
                                         xs -> head xs