David Menendez dave at zednenem.com
Mon Dec 29 21:10:17 EST 2008

On Mon, Dec 29, 2008 at 5:55 PM, Martijn van Steenbergen
<martijn at van.steenbergen.nl> wrote:
> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>