tree .hs

type WEdge w = (Vertex, (w, Vertex))
type WGraph w = Array Vertex [(w, Vertex)]
data WTree w a = WNode { rootLabelW :: a
                       , subForestW :: [(w, WTree w a)]
                       } deriving Show

buildWG :: Bounds -> [WEdge w] -> WGraph w
buildWG = accumArray (flip (:)) []

dfsWTree :: WGraph w -> Vertex -> WTree w Vertex
dfsWTree g u = go u u where
    go p u = WNode u [(w, go u v) | (w, v) <- g!u, v /= p]

instance Functor (WTree w) where
    fmap f = go where
        go (WNode a ts) = WNode (f a) [(w, go t) | (w, t) <- ts]