[Haskell-cafe] functional graphs

[Christian Maeder]

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