Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Dan Weston <westondan <at> imageworks.com>
Subject: Re: Infinite grid
Newsgroups: gmane.comp.lang.haskell.cafe
Date: Monday 5th January 2009 21:34:44 UTC (over 8 years ago)
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.
 
CD: 4ms