dfs

dfs.hs

import Prelude hiding (fail)

dfs
  :: a                     -- initial state
  -> path                  -- empty path
  -> (a -> [a])            -- branch function to generate states in next level
  -> (path -> a -> path)   -- function to add visited state to path
  -> (a -> Bool)           -- goal checker
  -> (a -> Bool)           -- failure checker, used for backtracking
  -> [path]                -- result is list of paths
dfs state emptyPath branch appendPath goal fail = search emptyPath state
  where
    search path state
      | fail state = []
      | goal state = [appendPath path state]
      | otherwise  = concatMap (search $ appendPath path state) (branch state)

main :: IO ()
main = do
    print $ dfs 4 [] (\x -> [x + 3, x + 4, x + 5]) (\p i -> p ++ [i]) (== 14) (> 14)
    return ()