grids

[ bsd3, data-structures, library ] [ Propose Tags ]

Arbitrary sized type-safe grids with useful combinators


[Skip to Readme]
Versions [faq] 0.1.0.0, 0.1.1.0, 0.2.0.0, 0.3.0.0, 0.4.0.0, 0.5.0.0, 0.5.0.1
Change log ChangeLog.md
Dependencies adjunctions, base (>=4.7 && <5), distributive, finite-typelits, lens, vector [details]
License BSD-3-Clause
Copyright Chris Penner
Author Chris Penner
Maintainer christopher.penner@gmail.com
Category Data Structures
Home page https://github.com/ChrisPenner/grids#readme
Bug tracker https://github.com/ChrisPenner/grids/issues
Source repo head: git clone https://github.com/ChrisPenner/grids
Uploaded by ChrisPenner at 2018-12-23T06:39:36Z
Distributions NixOS:0.5.0.1
Downloads 2454 total (5 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-12-23 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for grids-0.1.1.0

[back to package description]

Grids

Grids can have an arbitrary amount of dimensions, specified by a type-level list of Nats. They're backed by a single contiguous Vector and gain the associated performance benefits. Currently only boxed immutable vectors are supported, but let me know if you need other variants.

Here's how we might represent a Tic-Tac-Toe board:

data Piece = X | O deriving Show
toPiece n = if even n then X
                      else O

ticTacToe :: Grid [3, 3] Piece
ticTacToe = generate toPiece

You can collapse the grid down to nested lists! The output type of toNestedLists depends on your dimensions, e.g.:

  • Grid [3, 3] Piece will generate: [[Piece]]
  • Grid [2, 2, 2] Char will generate: [[[Char]]]
  • ...etc
λ> toNestedLists ticTacToe
[ [X,O,X]
, [O,X,O]
, [X,O,X]]

You can even create a grid from nested lists! fromNestedLists returns a grid if possible, or Nothing if the provided lists don't match the structure of the grid you specify:

λ> fromNestedLists [[1, 2], [3, 4]] :: Maybe (Grid '[2, 2] Int)
Just (Grid [[1,2]
           ,[3,4]])
λ> fromNestedLists [[1], [2]] :: Maybe (Grid '[2, 2] Int)
Nothing

Grids are Representable Functors, Applicatives, Foldable, and are Traversable!

You can do things like piecewise addition using their applicative instance:

λ> let g = generate id :: Grid '[2, 3] Int
λ> g
(Grid [[0,1,2]
      ,[3,4,5]])
λ> liftA2 (+) g g
(Grid [[0,2,4]
      ,[6,8,10]])
λ> liftA2 (*) g g
(Grid [[0,1,4]
      ,[9,16,25]])

Indexing

You can index into a grid using the Coord type family. The number of coordinates you need depends on the shape of the grid. The Coord is stitched together using the :# constructor from 1 or more Finite values. Each Finite value is scoped to the size of its dimension, so you'll need to prove that each index is within range (or just use finite to wrap an Integer and the compiler will trust you). Here's the type of Coord for a few different Grids:

Coord '[1] == Finite 1
Coord '[1, 2] == Finite 1 :# Finite 2
Coord '[1, 2, 3] == Finite 1 :# Finite 2 :# Finite 3

You can get a value at an index out using index from Data.Functor.Rep:

λ> let g = generate id :: Grid '[2, 3] Int
λ> g
(Grid [[0,1,2]
      ,[3,4,5]])
λ> g `index` (1 :# 1)
4
λ> g `index` (1 :# 0)
3
λ> g `index` (0 :# 2)
2

You can also use the cell Lens from Data.Grid.Lens to access and mutate indices:

λ> g ^. cell (0 :# 1)
1
λ> g & cell (0 :# 1) *~ 1000
(Grid [[0,1000,2],[3,4,5]])

Creation

You can generate a grid by providing a function over the integer position in the grid (generate) or by providing a function over the coordinate position of the cell (tabulate).

You can also use the fromList and fromNestedLists functions which return a Maybe (Grid dims a) depending on whether the input list is well formed.

  • fromList :: [a] -> Maybe (Grid dims a)
  • fromNestedLists :: NestedLists dims a -> Maybe (Grid dims a)
  • generate :: (Int -> a) -> Grid dims a
  • tabulate :: (Coord dims -> a) -> Grid dims a
  • pure :: a -> Grid dims a

Updating

Use either the cell lens, or fmap, applicative, traversable. For batch updates using the underlying Vector implementation use (//)

  • (//) :: Grid dims a -> [(Coord dims, a)] -> Grid dims a