# Infinite grid

9 messages
Open this post in threaded view
|

## Infinite grid

 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. _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 On Mon, Dec 29, 2008 at 3: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.No problem: let n = Node n n n n in nBut you probably want some additional data in each node, also, in which the problem becomes harder. Here is one quarter of it (it only extends to the north and east of the root node), you can fill in the rest.  I put in Debug.Trace so we can observe that they are actually shared.import Debug.Trace grid = nodes !! 0 !! 0   where  minus1 0 = 0  minus1 n = n-1  node i j = Node { north = nodes !! i !! (j+1)                  , east  = nodes !! (i+1) !! j                  , south = nodes !! i !! minus1 j                   , west  = nodes !! minus1 i !! j                  , contents = trace "Compute!" (i,j)                  }  nodes = [ [ node i j | j <- [0..] ] | i <- [0..] ] Luke _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 In reply to this post by Martijn van Steenbergen-2 Martijn van Steenbergen schrieb: > 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. :-) A dungeon game? :-) _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 In reply to this post by Luke Palmer-2 Luke Palmer wrote: > On Mon, Dec 29, 2008 at 3:55 PM, Martijn van Steenbergen > <[hidden email] > 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_KnotCheers,    Chris _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 In reply to this post by Martijn van Steenbergen-2 On Mon, Dec 29, 2008 at 5:55 PM, Martijn van Steenbergen <[hidden email]> 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 <[hidden email]> _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 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 > <[hidden email]> 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) > _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe
Open this post in threaded view
|

## Re: Infinite grid

 On Mon, Dec 29, 2008 at 9:29 PM, Dan Weston <[hidden email]> wrote: > I'm confused how this isn't just tantamount to using Data.Map > (Integer,Integer) a. Data.Map.Map is strict in terms of structure. The number of elements in the map must be known and less than (maxBound :: Int). That being said, I'm not sure what something like Grid a would be good for. Perhaps memoizing a function that took a list of moves as input. -- Dave Menendez <[hidden email]> _______________________________________________ Haskell-Cafe mailing list [hidden email] http://www.haskell.org/mailman/listinfo/haskell-cafe