[Haskell-cafe] functional graphs
Benja Fallenstein
benja.fallenstein at gmail.com
Sat Jan 19 13:13:50 EST 2008
Hi Christian,
On Jan 18, 2008 1:55 PM, Christian Maeder <Christian.Maeder at dfki.de> wrote:
> data CGraph a b = CGraph [a] (a -> a -> b)
>
> Can I define an instance for the fgl Graph class?
>
> I had no idea how to define empty (except using undefined).
Well, presumably the function does not need to be defined on values
not in the list, so returning an error is fair enough--
empty = CGraph [] (const $ error "Node not in graph")
I suppose you want to use the index in the list as the Node (= Int),
which should be fine, but you'll run into problems with mkGraph,
because you don't have an Eq constraint on a, so you can't implement
the function to pass to CGraph. Since mkGraph is required to have the
type
mkGraph :: [LNode a] -> [LEdge b] -> CGraph a b
for *all* a and b, you don't have a way to add an Eq constraint
anywhere, either.
So, no dice...
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)
- Benja
More information about the Haskell-Cafe
mailing list