# sized-grid

A way of working with grids in Haskell with size encoded at the type level.

# Quick tutorial

The core datatype of this library is `Grid (cs :: '[k]) (a :: *)`

. `cs`

is a type level list of coordinate types. We could use a single type level number here, but by using different types we can say what happened when we move outside the bounds of a grid. There are three different coordinate types provided.

`Ordinal n`

: An ordinal can be an integral number between 0 and n - 1. As numbers outside the grid are not possible, this has the most restrictive API. One can convert between an Ordinal and a number of ordinalToNum and numToOrdinal.

`HardWrap n`

: Like Oridnal, HardWrap can only hold intergral numbers between 0 and n - 1, but it allows a more permissive API by clamping values outside of its range. It is an instance of `Semigroup`

and `Monoid`

, where `mempty`

is 0 and `<>`

is addition.

`Periodic n`

: This is the most permissive. When a value is generated outside the given range, it wraps that around using modular arithmetic. Is is an instance of `Semigroup`

and `Monoid`

like `HardWrap`

, but also of `AdditiveGroup`

allowing negation.

`HardWrap`

and `Periodic`

are both instances of `AffineSpace`

, with their `Diff`

being `Integer`

. This means there are many occasions where one doesn't have to work directly with these values (which can be cumbersome) and can instead work with their differences as regular numbers.

The last type value of `Grid`

is the type of each element.

The other main type is `Coord cs`

, where `cs`

is, again, a type level list of coordinate types. For example, `Coord '[Periodic 3, HardWrap 4]`

is a coordinate in a 3 by 4 2D space. The different types (`Periodic`

and `HardWrap`

) tell how to handle combining theses different numbers. `Coord cs`

is an instance of `Semigroup`

, `Monoid`

and `AdditiveGroup`

as long as each of the coordinates is also an instance of that typeclass. `Coord`

is also an instance of of `AffineSpace`

, where `Diff`

is a n-tuple, meaning we can pattern match and do all sorts of nice things.

For working directly with `Coord`

s, one can construct them with `singleCoord`

and `appendCoord`

and consume and update them with `coordHead`

and `coordTail`

. They are also instances of `FieldN`

from lens, allowing one to directly update or get a certain dimension.

There is a deliberately small number of functions that work over `Grid`

: we instead opt for using typeclasses to create the required functionality. `Grid`

is an instance of the following types (with some required constraints):

`Functor`

: Update all values in the grid with the same function
`Applicative`

: As the size of the grid is statically known, `pure`

just creates a grid with the same element at each point. `<*>`

combines the grids point wise.
`Monad`

: I'm not sure if there is much of a need for this, but an instance exists.
`Foldable`

: Combine each element of the grid
`Traverse`

: Apply an applicative function over the grid
`IndexedFunctor`

, `IndexedFoldable`

and `IndexedTraversable`

: Like `Functor`

, `Foldable`

and `Traversable`

, but with access to the position at each point. These are from the lens package
`Distributive`

: Like `Traversable`

, but the other way round. Allows us to put a functor inside the grid
`Representable`

: `Grid cs a`

is isomorphic `Coord cs -> a`

, so we can `tabulate`

and `index`

to make this conversion

We also have a `FocusedGrid`

type, which is like `Grid`

but has a certain focused position. This means that we lose many instances, but we gain `Comonad`

and `ComonadStore`

.

When dealing with areas around `Coord`

s, we can use `moorePoints`

and `vonNeumanPoints`

to generate Moore and von Neuman neighbourhoods. Note that these include the center point.

We introduce two new typeclasses: `IsCoord`

and `IsGrid`

. `IsGrid`

has `gridIndex`

, which allows us to get a single element of the grid and lenses to convert between `FocusedGrid`

and `Grid`

. `IsCoord`

has `CoordSized`

, which is the size of the coord and an iso to convert between `Ordinal`

and the `Coord`

.

# Example - Game of Life

As is traditional for anything with grids and comonads in Haskell, we can reimplement Conway's Game of Life.

This is a literate Haskell file, so we start by turning on some language extensions, importing our library and some other utilities.

```
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE MonoLocalBinds #-}
{-# LANGUAGE DataKinds #-}
import SizedGrid
import Control.Comonad
import Control.Lens
import Control.Comonad.Store
import Data.AdditiveGroup
import Data.AffineSpace
import Data.Distributive
import Data.Functor.Rep
import Data.Semigroup (Semigroup(..))
import GHC.TypeLits
import qualified GHC.TypeLits as GHC
import System.Console.ANSI
```

We create a datatype for alive or dead.

```
data TileState = Alive | Dead deriving (Eq,Show)
```

We encode the rules of the game via a step function.

```
type Rule = TileState -> [TileState] -> TileState
gameOfLife :: Rule
gameOfLife here neigh =
let aliveNeigh = length $ filter (== Alive) neigh
in if | here == Alive && aliveNeigh `elem` [2,3] -> Alive
| here == Dead && aliveNeigh == 3 -> Alive
| otherwise -> Dead
```

We can then write a function to apply this to every point in a grid.

```
applyRule ::
( All IsCoord cs
, All Monoid cs
, All Semigroup cs
, All AffineSpace cs
, All Eq cs
, AllDiffSame Integer cs
, AllSizedKnown cs
, IsGrid cs (grid cs)
)
=> Rule
-> grid cs TileState
-> grid cs TileState
applyRule rule = over asFocusedGrid $
extend $ \fg -> rule (extract fg) $ map (\p -> peek p fg) $
filter (/= pos fg) $ moorePoints (1 :: Integer) $ pos fg
```

We can create a simple drawing function to display it to the screen.

```
displayTileState :: TileState -> Char
displayTileState Alive = '#'
displayTileState Dead = '.'
displayGrid :: (KnownNat (CoordSized x), KnownNat (CoordSized y)) =>
Grid '[x, y] TileState -> String
displayGrid = unlines . collapseGrid . fmap displayTileState
```

Let's create a glider, and watch it move!

```
glider ::
( KnownNat (CoordSized x GHC.* CoordSized y)
, Semigroup x
, Semigroup y
, Monoid x
, Monoid y
, IsCoord x
, IsCoord y
, AffineSpace x
, AffineSpace y
, Diff x ~ Integer
, Diff y ~ Integer
)
=> Coord '[x,y]
-> Grid '[x,y] TileState
glider offset = pure Dead
& gridIndex (offset .+^ (0,-1)) .~ Alive
& gridIndex (offset .+^ (1,0)) .~ Alive
& gridIndex (offset .+^ (-1,1)) .~ Alive
& gridIndex (offset .+^ (0,1)) .~ Alive
& gridIndex (offset .+^ (1,1)) .~ Alive
```

We can now make our glider run!

```
run =
let start :: Grid '[Periodic 10, Periodic 10] TileState
start = glider (mempty .+^ (3,3))
doStep grid = do
clearScreen
putStrLn $ displayGrid grid
_ <- getLine
doStep $ applyRule gameOfLife grid
in doStep start
main = return ()
```