Luke Palmer wrote:

On Mon, Dec 29, 2008 at 3:55 PM, Martijn van Steenbergen mailto:martijn@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.

No problem:

let n = Node n n n n in n

But you probably want some additional data in each node, also, in which the problem becomes harder.

The solution very much depends on how the data is initialized / computed / obtained. Note that one can put an IORef into the Node to allow for mutable value. Also, see if you need something akin to mkDList at http://haskell.org/haskellwiki/Tying_the_Knot Cheers, Chris

Henning Thielemann wrote:

A dungeon game? :-)

Yes. :-) Thank you all for your answers! I especially like David's no-intermediate-structure solution because it allows for defining the area in terms of neighbours instead of needing an index on the rooms. Now that I have core functionality in my game I want to try and build some interesting areas, such as infinite ones: a infinite grid, or an N-dimensional Hilbert curve. Because rooms are mutable, I am building them inside a state monad and use ids: mkRoom :: M RoomId addExit :: RoomId -> Exit -> M () type Exit = (String, RoomId) I thought my original question would give me some ideas on how to construct infinite areas, but this monadic interface complicates things somewhat. If I create all rooms at once, runState never returns, so I will have to create them lazily, perhaps by changing: type Exit = M (String, RoomId) But I think in addition to that I will also needs refs, so that the monadic computation can check using a ref whether it's created its target room before. I will have to experiment and think on this some more. Martijn.

I'm confused how this isn't just tantamount to using Data.Map (Integer,Integer) a. The essential problem is that you have an algebra acting on a topology. The algebra is easily rewritten to an efficient form, but a sequence of topological actions is not, because it is not sufficiently forgetful of path, due to the inherent inability of F-algebras (or maybe lack of cleverness on our part?) to create a data structure that allows a 2D zipper without duplication. Unlike a 1D zipper, there always exists a path from an updated element to every other element that doesn't cross the zipped path, so everything becomes tainted (like pulling on the thread of an unhemmed garment). In other words, a 1D space can be encoded as a binary tree or two lists, giving either global O(log n) or local O(1) access, respectively. A 2D space can also be encoded as a quadtree giving global O(log n) access, but I can't imagine a zipper structure that efficiently can cut and splice in constant time as it moves through. Or have I (once again) completely missed the obvious? Dan David Menendez wrote:

On Mon, Dec 29, 2008 at 5:55 PM, 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'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)