深さ優先探索のHaskell版(モナド変換子練習用)

dfs.hs

import Control.Monad.Reader
import Control.Monad.State
import qualified Data.Map as Map

data Elem = A | B | C | D | E | F | G
          deriving (Show, Eq, Ord)

type Visited = [Elem]
type AdjMap  = Map.Map Elem [Elem]

testData = Map.fromList [  (A, [B,C,E])
                         , (B, [D,F])
                         , (C, [G])
                         , (D, [])
                         , (E, [F])
                         , (F, [])
                         , (G, [])]

depthFirstSearch :: Elem -> StateT Visited (Reader AdjMap) [Elem]
depthFirstSearch begin = do
  visited <- get
  if elem begin visited
    then return []
    else do
    put (begin : visited)
    adjmap <- lift ask
    ll <- mapM depthFirstSearch (adjmap Map.! begin)
    return $ (concat ll) ++ [begin]

main = do
  let (l, _) = runReader (runStateT (depthFirstSearch A) []) testData
  print l