On Mon, Dec 29, 2008 at 5:55 PM, Martijn van Steenbergen
Hello,
I would like to construct an infinite two-dimensional grid of nodes, where a node looks like this:
data Node = Node { north :: Node , east :: Node , south :: Node , west :: Node }
in such a way that for every node n in the grid it doesn't matter how I travel to n, I always end up in the same memory location for that node.
I'm curious to know what you would do with it, actually. Once you have
such a structure, you can't really modify it because that would
require copying the entire thing, and you can't fill it with IORefs,
as ChrisK suggested, because you would need an infinite supply of
them.
Here's my own solution, which is longer than Luke Palmer's but doesn't
rely on an intermediate data structure.
data Node a = Node
{ contents :: a
, north :: Node a
, south :: Node a
, east :: Node a
, west :: Node a
}
grid :: (Integer -> Integer -> a) -> Node a
grid f = origin
where
origin = Node
{ contents = f 0 0
, north = growNorth 0 1 origin
, south = growSouth 0 (-1) origin
, east = growEast 1 origin
, west = growWest (-1) origin
}
growEast x w = self
where
self = Node
{ contents = f x 0
, north = growNorth x 1 self
, south = growSouth x (-1) self
, east = growEast (x+1) self
, west = w
}
growWest x e = self
where
self = Node
{ contents = f x 0
, north = growNorth x 1 self
, south = growSouth x (-1) self
, east = e
, west = growWest (x+1) self
}
growNorth x y s = self
where
self = Node
{ contents = f x y
, north = growNorth x (y-1) self
, south = s
, east = north (east s)
, west = north (west s)
}
growSouth x y n = self
where
self = Node
{ contents = f x y
, north = n
, south = growSouth x (y-1) self
, east = south (east n)
, west = south (west n)
}
--
*Main Debug.Trace> let o = grid (\x y -> trace ("compute " ++ show (x,y)) (x,y))
*Main Debug.Trace> contents o
compute (0,0)
(0,0)
*Main Debug.Trace> contents . west . south . east . north $ o
(0,0)
*Main Debug.Trace> contents . east . north $ o
compute (1,1)
(1,1)
*Main Debug.Trace> contents . north . east $ o
(1,1)
--
Dave Menendez