data SF a = SS a | FF

------------------------------------------------------------
--
--  Basic search for all solutions (note will get a different 
--  for each search path.
--
------------------------------------------------------------

search::(s -> SF [s]) -> s -> [s]
search f start = case f start of 
                        FF -> [start]
                        SS states -> do s' <- states
                                        ans <- search f s'
                                        return ans

------------------------------------------------------------
--
--  An example search problem on a small graph.
--
------------------------------------------------------------

data Nodes = A|B|C|D|E|F
    deriving (Show, Eq)

trans:: Nodes -> SF [Nodes]
trans A = SS [B,C]
trans B = SS [F,D]
trans C = SS [D,E]
trans D = FF
trans E = SS []
trans F = SS []

-- search trans A

-----------------------------------------------------------
--
-- Setting up the state monad
--
-----------------------------------------------------------

data SM s a = Sm (s -> (a,s))

runSM:: (SM s a) -> (s -> (a,s))
runSM (Sm h) = h

-- For modifying the state 
modSM::(s -> s) -> (SM s ())
modSM f = Sm (\st -> ((),f st))


instance Monad (SM s) where
     return y = Sm (\s -> (y,s))
     (Sm f) >>= g = Sm (\s -> (\(y,s') -> runSM (g y) s') (f s)) where

       
----------------------------------------------------------------------------
--
-- Counting search: searching for all the solutions while counting the number 
-- of guesses which are made.
--
----------------------------------------------------------------------------

count_search::(s -> SF [s]) -> s -> ([s],Integer)
count_search trans s = (runSM (count_srch trans s)) 0 where
     -- Searching using the state monad to count the search steps
     -- The counting search from a single state:
     count_srch::(s -> SF [s]) -> s -> (SM Integer [s])
     count_srch trans s = case trans s of 
                               FF -> return [s]
                               SS ss -> count_srchs trans ss
     -- The counting search from a list of states;
     count_srchs:: (s -> SF [s]) -> [s] -> (SM Integer [s])
     count_srchs trans [] = return []
     count_srchs trans (s:ss) = do () <- modSM (\n -> n+1)   
        -- counts one more guess by incrementing the counter in the state
                                   s' <- count_srch trans s
                                   ss' <- count_srchs trans ss
                                   return (s'++ss')

-- count_search trans A