How would you implement a Grid in a functional language?

Question

I am interrested in different ways of implementing a constant grid in a functional language. A perfect solution should provide traversal in pesimistic constant time per step and not use imperative constructs (laziness is ok). Solutions not quite fulfilling those requirements are still welcome.

My proposal is based on four-way linked nodes like so

A fundamental operation would be to construct a grid of given size. It seems that this operation will determine the type, i.e. which directions will be lazy (obviously this data structure cannot be achieved without laziness). So I propose (in OCaml)

type 'a grid =
  | GNil
  | GNode of 'a * 'a grid Lazy.t * 'a grid Lazy.t * 'a grid * 'a grid

With references ordered: left, up, right, down. Left and up are suspended. I then build the grid diagonal-wise

Here is a make_grid function that constructs a grid of given size with the coordinate tuples as node values. Please note that gl, gu, gr, gd functions allow walking on a grid in all directions and if given GNil, will return GNil.

let make_grid w h =
  let lgnil = Lazy.from_val GNil in
  let rec build_ur x y ls dls = match ls with
    | l :: ((u :: _) as ls') ->
      if x = w && y = h then
        GNode ((x, y), l, u, GNil, GNil)
      else if x < w && 1 < y then
        let rec n = lazy (
          let ur = build_ur (x + 1) (y - 1) ls' (n :: dls) in
          let r = gd ur in
          let d = gl (gd r)
          in GNode ((x, y), l, u, r, d)
        )
        in force n
      else if x = w then 
        let rec n = lazy (
          let d = build_dl x (y + 1) (n :: dls) [lgnil]
          in GNode ((x, y), l, u, GNil, d)
        )
        in force n
      else
        let rec n = lazy (
          let r = build_dl (x + 1) y (lgnil :: n :: dls) [lgnil] in
          let d = gl (gd r)
          in GNode ((x, y), l, u, r, d)
        )
        in force n
    | _ -> failwith "make_grid: Internal error"
  and build_dl x y us urs = match us with
    | u :: ((l :: _) as us') ->
      if x = w && y = h then
        GNode ((x, y), l, u, GNil, GNil)
      else if 1 < x && y < h then
        let rec n = lazy (
          let dl = build_dl (x - 1) (y + 1) us' (n :: urs) in
          let d = gr dl in
          let r = gu (gr d)
          in GNode ((x, y), l, u, r, d)
        )
        in force n
      else if y = h then
        let rec n = lazy (
          let r = build_ur (x + 1) y (n :: urs) [lgnil]
          in GNode ((x, y), l, u, r, GNil)
        )
        in force n
      else (* x = 1 *)
        let rec n = lazy (
          let d = build_ur x (y + 1) (lgnil :: n :: urs) [lgnil] in
          let r = gu (gr d)
          in GNode ((x, y), l, u, r, d)
        )
        in force n
    | _ -> failwith "make_grid: Internal error"
  in build_ur 1 1 [lgnil; lgnil] [lgnil]

It looks pretty complicated as it has to separately handle case when we're going up and when we're going down – build_ur and build_dl auxiliary functions respectively. The build_ur function is of type

build_ur :
  int -> int ->
  (int * int) grid Lazy.t list -> 
  (int * int) grid Lazy.t list -> (int * int) grid

It construct a node, given the current position x and y, the list of suspended elements of previous diagonal ls, the list of suspended previous elements of current diagonal urs. The name ls comes from the fact that the first element on ls is the left neighbour of current node. The urs list is needed for construction of the next diagonal.

The build_urs function proceeds with building the next node on the up-right diagonal, passing the current node in a suspension. The left and up neighbour are taken from ls and the right and down neighbours can be accessed through the next node on the diagonal.

Note that I put a bunch of GNils on the urs and ls lists. This is made to always ensure that build_ur and build_dl can consume at least two elements from those lists.

The build_dl function works analogously.

This implementation seems overly complicated for such a simple data structure. In fact I'm suprised it works cause I was driven by faith when writing it and am unable to comprehend completely why it works. Therefore I would like to know a simpler solution.

I was considering building the grid row-wise. This approach has less border cases but I can't eliminate the need of building subsequent rows in different directions. It's because when I go to the end with a row and would like to start building another from the beginning, I would have to somehow know the down node of the first node in current row, which I seemingly can't know until I return from the current function call. And if I can't eliminate bi-directionality, I would need two inner node constructiors: one with suspended left and top and the other with suspended right and top.

Also, here is a gist of this implementation along with omitted functions: https://gist.github.com/mkacz91/0e63aaa2a67f8e67e56f

Answer 1

The datastructure you are looking for if you want a functional solution is a zipper. I've written the rest of the code in Haskell because I find it more to my taste but it's easily ported to OCaml. Here's a gist without the interleaved comments.

{-# LANGUAGE RecordWildCards #-}

module Grid where

import Data.Maybe

We can start by understanding the datastructure for just lists: you can think of a zipper as a pointer deep inside a list. You have wathever is on the left of the element you point at, then the element you point at and finally whatever is on the right.

type ListZipper a = ([a], a, [a])

Given a list and an integer n, you can focus on the element which is at position n. Of course, if n is greater than the lenght of the list, then you just fail. One important thing to notice is that the left part of the list is stored backwards: moving the focus to the left will therefore be possible in constant time. As will moving to the right.

focusListAt :: Int -> [a] -> Maybe (ListZipper a)
focusListAt = go []
  where
    go _   _ []        = Nothing
    go acc 0 (hd : tl) = Just (acc, hd, tl)
    go acc n (hd : tl) = go (hd : acc) (n - 1) tl

Let's move on to Grids now. A Grid will just be a list of rows (lists).

newtype Grid a = Grid { unGrid :: [[a]] }

A zipper for a Grid is now given by a grid representing everything above the current focus, another representing everything below it, and a list zipper (advanced level: notice that this looks a bit like nested list zippers & could be reformulated in more generic terms).

data GridZipper a =
  GridZipper { above :: Grid a
             , below :: Grid a
             , left  :: [a]
             , right :: [a]
             , focus :: a }

By focusing on the right row first, and then the right element we may focus a Grid at some coordinates x and y.

focusGridAt :: Int -> Int -> Grid a -> Maybe (GridZipper a)
focusGridAt x y g = do
  (before, line , after) <- focusListAt x $ unGrid g
  (left  , focus, right) <- focusListAt y line
  let above = Grid before
  let below = Grid after
  return GridZipper{..}

Once we have a zipper, we can move around easily. The code for going either left or right is not suprisingly rather similar:

goLeft :: GridZipper a -> Maybe (GridZipper a)
goLeft g@GridZipper{..} =
  case left of
    []      -> Nothing
    (hd:tl) -> Just $ g { focus = hd, left = tl, right = focus : right }

goRight :: GridZipper a -> Maybe (GridZipper a)
goRight g@GridZipper{..} =
  case right of
    []      -> Nothing
    (hd:tl) -> Just $ g { focus = hd, left = focus : left, right = tl }

When going up or down, we have to be a bit careful because we need to focus on the spot right above (or below) the one we left in the new row. We also have to reassemble the previous row we were focused onto into a good old list (by appending the reversed left to focus : right).

goUp :: GridZipper a -> Maybe (GridZipper a)
goUp GridZipper{..} = do
  let (line : above')     = unGrid above
  let below'              = (reverse left ++ focus : right) : unGrid below
  (left', focus', right') <- focusListAt (length left) line
  return $ GridZipper { above = Grid above'
                      , below = Grid below'
                      , left  = left'
                      , right = right'
                      , focus = focus' }

goDown :: GridZipper a -> Maybe (GridZipper a)
goDown GridZipper{..} = do
  let (line : below')     = unGrid below
  let above'              = (reverse left ++ focus : right) : unGrid above
  (left', focus', right') <- focusListAt (length left) line
  return $ GridZipper { above = Grid above'
                      , below = Grid below'
                      , left  = left'
                      , right = right'
                      , focus = focus' }

Finally, I've also added a couple of helper functions to generate grids (with every cell containing a pair of its coordinates) and instances to be able to display grids and zippers in a terminal.

mkGrid :: Int -> Int -> Grid (Int, Int)
mkGrid m n = Grid $ [ zip (repeat i) [0..n-1] | i <- [0..m-1] ]

instance Show a => Show (Grid a) where
  show = concatMap (('\n' :) . concatMap show) . unGrid

instance Show a => Show (GridZipper a) where
  show GridZipper{..} =
    concat [ show above, "\n"
           , concatMap show (reverse left)
           , "\x1B[33m[\x1B[0m",  show focus, "\x1B[33m]\x1B[0m"
           , concatMap show right
           , show below ]

main creates a small grid of size 5*10, focuses on the element at coordinates (2,3) and moves around a bit.

main :: IO ()
main = do
  let grid1 = mkGrid 5 10
  print grid1
  let grid2 = fromJust $ focusGridAt 2 3 grid1
  print grid2
  print $ goLeft =<< goLeft =<< goDown =<< goDown grid2