How do I implement the Grid in a functional language?
I am interested in different ways to implement a constant grid in a functional language. The ideal solution should provide a bypass in the pesimic time constant for each step and not use imperative constructs (laziness is normal). Solutions that do not quite meet these requirements are still welcome.
My suggestion is based on four-way connected nodes like
The basic operation would be to build a mesh of a given size. It seems that this operation will determine the type, i.e. Which directions would be lazy (obviously this data structure cannot be achieved without laziness). So I suggest (in OCaml)
type 'a grid =
| GNil
| GNode of 'a * 'a grid Lazy.t * 'a grid Lazy.t * 'a grid * 'a grid
With ordered links: left, up, right, down. Left and up are suspended. Then I create a grid diagonally
Here is a function make_grid
that plots a grid of a given size with coordinate tuples as node values. Note that the functions gl
, gu
, gr
, gd
let go of the grid in all directions and if asked 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 rather complicated, since it must separately handle the case, when we go up and when we go down - helper functions build_ur
and build_dl
accordingly. The function build_ur
is of type
build_ur :
int -> int ->
(int * int) grid Lazy.t list ->
(int * int) grid Lazy.t list -> (int * int) grid
It will build a node given the current position x
and y
, a list of blocked items from the previous diagonal ls
, a list of paused previous items from the current diagonal urs
. The name ls
comes from the fact that the first element ls
is not the left neighbor of the current node. The list is urs
needed to build the next diagonal.
The function build_urs
works on the string of the next node in the right-right diagonal, passing the current node in the pendant. The left and top neighbors are taken from ls
, while the right and down neighbors can be accessed through the next diagonal node.
Note that I put a bunch GNil
in the list urs
and ls
. This is done in order to always ensure that build_ur
and build_dl
can consume at least two elements of these lists.
" data-src="/img/20c350124b7cc533027e4ec7f15c0a75.png" class=" lazyloaded" src="https://fooobar.com//img/20c350124b7cc533027e4ec7f15c0a75.png">
The function build_dl
works the same way.
This implementation seems too complicated for such a simple data structure. I'm actually surprised it works because I was led by faith when I wrote it and can't fully understand why it works. So I would like to know a simpler solution.
I've considered meshing in different ways. This approach has less edge cases, but I cannot eliminate the need to create subsequent lines in different directions. This is because when I end a line and want to start building from the beginning, I need to somehow learn about the bottom node of the first node in the current line, which I don't seem to know until I return from the current function call. And if I can't eliminate bidirectionality, I'll need two internal node constructors, one with left and top suspended, and another with right and top suspended.
Also, here is the gist of this implementation along with the missing features: https://gist.github.com/mkacz91/0e63aaa2a67f8e67e56f
source to share
A required data structure if you want a functional solution, zipper . I wrote the rest of the code in Haskell because I find it more to my liking, but it is easily portable to OCaml. Here's the gist, without alternating comments.
{-# LANGUAGE RecordWildCards #-} module Grid where import Data.Maybe
We can start by understanding the data structure for lists only: you can think of lightning as a pointer deep within a list. You have what's to the left of the element you are pointing to, then the element you are pointing to, and finally everything to the right.
type ListZipper a = ([a], a, [a])
Given a list and an integer n
, you can focus on the element that is in position n
. Of course, if n
more than the length of the list, you just fail. It is important to note that the left side of the list is stored in the opposite direction: therefore, moving focus to the left will be possible at a constant time. How will move 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
Now let's move on to the mesh. A Grid
will just be a list of strings (lists).
newtype Grid a = Grid { unGrid :: [[a]] }
The zipper for is Grid
now given by a grid representing all of the above
current focus, another is all there is below
and the zipper list (advanced level: note that this looks a bit like a nested zipper list and could be reformulated in more general terms).
data GridZipper a = GridZipper { above :: Grid a , below :: Grid a , left :: [a] , right :: [a] , focus :: a }
By focusing first on the right line and then on the right element, we can focus a Grid
on 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 lightning, we can move around easily. The code for going either left or right is not surprisingly 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 moving up or down, we need to be a little careful because we need to focus on the spot directly above (or below) the one we left on the new line. We also need to collect the previous line we focused on into a good old list (by adding the reverse 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 also added a few helper functions to generate grids (with each cell containing a pair of its coordinates) and instances to be able to display grids and lightning bolts in the 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 5 * 10 grid, focuses on the element at coordinates (2,3), and moves slightly.
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
source to share
A simple solution for implementing infinite grids is to use a hash table indexed by pairs of coordinates.
Below is an example implementation that does not check for integer overflow:
type 'a cell = {
x: int; (* position on the horizontal axis *)
y: int; (* position on the vertical axis *)
value: 'a;
}
type 'a grid = {
cells: (int * int, 'a cell) Hashtbl.t;
init_cell: int -> int -> 'a;
}
let create_grid init_cell = {
cells = Hashtbl.create 10;
init_cell;
}
let hashtbl_get tbl k =
try Some (Hashtbl.find tbl k)
with Not_found -> None
(* Check if we have a cell at the given relative position *)
let peek grid cell x_offset y_offset =
hashtbl_get grid.cells (cell.x + x_offset, cell.y + y_offset)
(* Get the cell at the given relative position *)
let get grid cell x_offset y_offset =
let x = cell.x + x_offset in
let y = cell.y + y_offset in
let k = (x, y) in
match hashtbl_get grid.cells k with
| Some c -> c
| None ->
let new_cell = {
x; y;
value = grid.init_cell x y
} in
Hashtbl.add grid.cells k new_cell;
new_cell
let left grid cell = get grid cell (-1) 0
let right grid cell = get grid cell 1 0
let down grid cell = get grid cell 0 (-1)
(* etc. *)
source to share