views:

113

answers:

2

I want to represent a graph in Haskell in the following manner:

For each node I want to store it's value and a list of adjacent nodes,the problem which i'm having difficulties with is that I want the adjacent nodes to be stored as references to other nodes.

For example: I want node ny to be stored as („NY“ (l p)) where l and p are adjacent nodes,and not as („NY“ („London“ „Paris“)).
I tried something like this :

data Node a = Node { value :: a
                   , neighbors :: [Node a]
                   }deriving (Show)

let n1 = Node {value=1, neighbors=[n2]}
let n2 = Node {value=1, neighbors=[n1 n3]}
let n3 = Node {value=1, neighbors=[n2]}

But i get en error in let,What am I doing wrong ?

+6  A: 

Two problems:

  1. let is an expression form and at top level the compiler is expecting a declaration form.

  2. You need a single nest of bindings; by using three lets, you've split the definitions into three separate scopes.

The following code compiles, and when I ask for n1, I get an infinite string printout as expected:

module Letnest 
where
data Node a = Node { value :: a
                   , neighbors :: [Node a]
                   } deriving (Show)

n1 = Node {value=1, neighbors=[n2]}
n2 = Node {value=1, neighbors=[n1, n3]}
n3 = Node {value=1, neighbors=[n2]}
Norman Ramsey
Note that `n1` and `n3` are completely indistinguishable (since they have the same definition) which, depending on your application, may be a problem with this representation.
Reid Barton
+3  A: 

I wouldn't represent a graph this way. Store the nodes in a Map or an Array and refer to them by their keys instead of directly pointing to them. This would be much easier to save, load, maintain, and work with.

For some problems with your current representation:

Reid Barton commented:

Note that n1 and n3 are completely indistinguishable (since they have the same definition) which, depending on your application, may be a problem with this representation.

(there is no is comparison a la Python in Haskell)

Norman Ramsey noticed:

I get an infinite string printout

yairchu
I woudn't represent a graph like this as well but that's what my homework says :)
John Retallack
@John Retallack: oh. I hope that the next homework question is about how else you could represent a graph.
yairchu