[Haskell-cafe] Infinite grid

[Dan Weston]

I think I found a solution to this, if you're still looking for one. See 
attached code. It uses a rose tree zipper where tree depth is manhattan 
distance from origin and forest width is nodes around concentric 
diamonds. The code is straightforward. Polar coords (RK) are stored in 
node label, with conversion to/from cartesian calculated on the fly (but 
may also be stored in label if speed is more important than time).

Cyclic closed loop tests like your f below run in constant space for me.

Dan Weston

Martijn van Steenbergen 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 suspect another way of saying that is that
> 
>> let f = f . north . east . south . west in f origin
> 
> should run in constant space. I hope this makes the problem clear. :-)
> 
> How do I do this?
> 
> Thanks in advance,
> 
> Martijn.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: GridZipper.hs
Type: text/x-haskell
Size: 10244 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20090105/01fe7b59/GridZipper.bin