[Haskell-cafe] functional graphs
Christian Maeder
Christian.Maeder at dfki.de
Mon Jan 21 04:57:41 EST 2008
Benja Fallenstein wrote:
> However, if you'd be able to live with
>
> data CGraph a b = CGraph [LNode a] (Node -> Node -> b)
>
> then you should be able to write the instance like this--
>
> instance Graph CGraph where
> empty = CGraph [] (const $ error "Node not in graph")
> isEmpty (CGraph xs _) = null xs
> labNodes (CGraph xs _) = xs
> mkGraph nodes edges = CGraph nodes f where
> f x y = fromMaybe (error "Edge not found") (lookup (x,y) edges')
> edges' = map (\(x,y,l) -> ((x,y),l)) edges
> match x (CGraph nodes f) = case lookup x nodes of
> Nothing -> (Nothing, CGraph nodes f)
> Just l ->
> let nodes' = filter ((/= x) . fst) nodes
> left = map (\(y,_) -> (f y x, y)) nodes'
> right = map (\(y,_) -> (f x y, y)) nodes'
> in (Just (left, x, l, right), CGraph nodes' f)
Thanks for pointing out this proposal. The actual problem is mkGraph
that needs all the many edges created beforehand (that's what I wanted
to avoid).
Cheers Christian
More information about the Haskell-Cafe
mailing list