[Haskell-cafe] Infinite grid

[David Menendez]

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)

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>