[Haskell-cafe] Infinite grid

Dan Weston westondan at imageworks.com
Mon Dec 29 21:29:23 EST 2008


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
> <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)
> 




More information about the Haskell-Cafe mailing list