sized-grid: Multidimensional grids with sized specified at compile time

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

`size-grid` allows you to make finite sized grids and have their size and shape confirmed at compile time

Consult the readme for a short tutorial and explanation.

[Skip to Readme]


Change log
Dependencies adjunctions (>=4.4 && <4.5), aeson (>= && <1.3), base (>=4.9 && <4.12), comonad (>=5.0.3 && <5.1), constraints (>=0.10 && <0.11), distributive (>=0.5.3 && <0.6), generics-sop (>= && <0.4), lens (>=4.16.1 && <4.17), mtl (>=2.2.2 && <2.3), random (>=1.1 && <1.2), vector (>= && <0.13), vector-space (>=0.13 && <0.14) [details]
License MIT
Author edwardwas
Category Data
Home page
Bug tracker
Uploaded by edwardwas at 2018-05-10T10:05:23Z




Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Readme for sized-grid-

[back to package description]

Build Status



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.

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 Coords, 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):

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 Coords, 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 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
       , KnownNat (MaxCoordSize 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 * 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
          putStrLn $ displayGrid grid
          _ <- getLine
          doStep $ applyRule gameOfLife grid
    in doStep start

main = return ()