dependencyclosed.hs

module Main where

import Data.Maybe (fromJust)
import Data.List (nub, intersect)
import Control.Monad.Writer

-- Modules in topological order, i.e.
-- a module must appear after all of its
-- dependencies
dependencies = [
 ("Base",[]),
 ("DateTime",["Base"]),
 ("Format",["Base"]),
 ("Iter",["Base"]),
 ("Async",["Base"]),
 ("DOM",["Base"]),
 ("Style",["DOM"]),
 ("Color",["Style"]),
 ("Logging",["Base"]),
 ("LoggingPane",["Logging"]),
 ("Selector",["Style"]),
 ("Signal",["Style"]),
 ("Visual",["Color"]),
 ("DragAndDrop",["Iter","Signal","Visual"]),
 ("Sortable",["DragAndDrop"])
 ]

modules = map fst dependencies

-- Simple transitive closure
closure :: [String] -> [String]
closure ms = 
    let missing = nub $ filter (not . flip elem ms) 
                  $ concatMap (fromJust . flip lookup dependencies) ms
    in
      if null missing
         then ms
         else closure (ms ++ missing)

antichains :: Writer [[String]] ()
antichains = antichains' [] modules
    where
      antichains' :: [String] -> [String] -> (Writer [[String]] ())
      antichains' ac [] = tell [ac]
      antichains' ac (candidate:rest) =
          do if ac `accepts` candidate
                then antichains' (candidate:ac) rest
                else return ()
             antichains' ac rest
      chain `accepts` candidate = null $ intersect (closure [candidate]) chain

main :: IO ()
main = do mapM_ (putStrLn . show . closure) $ snd $ runWriter antichains