grids 0.2.0.0 → 0.3.0.0

raw patch · 19 files changed

+1042/−231 lines, 19 filesdep +comonaddep +deepseqdep +gaugedep −finite-typelitsPVP ok

version bump matches the API change (PVP)

Dependencies added: comonad, deepseq, gauge, grids, hspec, singletons

Dependencies removed: finite-typelits

API changes (from Hackage documentation)

Files

• ChangeLog.md +9/−0
• README.md +14/−2
• benchmarks/Benchmarks.hs +15/−0
• grids.cabal +61/−4
• src/Data/Grid.hs +50/−197
• src/Data/Grid/Examples/Conway.hs +34/−0
• src/Data/Grid/Examples/Intro.hs +71/−0
• src/Data/Grid/Internal/Convolution.hs +158/−0
• src/Data/Grid/Internal/Coord.hs +123/−0
• src/Data/Grid/Internal/Errors.hs +11/−0
• src/Data/Grid/Internal/Grid.hs +124/−0
• src/Data/Grid/Internal/Identity.hs +18/−0
• src/Data/Grid/Internal/Lens.hs +27/−0
• src/Data/Grid/Internal/Nest.hs +40/−0
• src/Data/Grid/Internal/NestedLists.hs +45/−0
• src/Data/Grid/Internal/Pretty.hs +18/−0
• src/Data/Grid/Internal/Transpose.hs +98/−0
• src/Data/Grid/Lens.hs +0/−28
• test/Spec.hs +126/−0

@@ -1,3 +1,12 @@ # Changelog for grids +## 0.3.0.0+- Huge changes to Grid types, Coord types.+- Add Convolution combinators+- Add Permutation combinators++## 0.2.0.0+- Add docs+- Initial release+ ## Unreleased changes

@@ -3,14 +3,26 @@ [HACKAGE](http://hackage.haskell.org/package/grids)  Grids can have an arbitrary amount of dimensions, specified by a type-level-list of `Nat`s. They're backed by a single contiguous Vector and gain the+list of `Nat`s.++Each grid has Functor, Applicative, and Representable instances making it easy to do **Matlab-style** matrix programming. `liftA2 (+)` does piecewise addition, etc.++By combining with `Control.Comonad.Representable.Store` you can do context-wise **linear transformations** for things like **Image Processing** or **Cellular Automata**.++All in a typesafe package!++Still working out the best interface for this stuff, feedback is appreciated!++Grids 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:+Here's how we might represent a Tic-Tac-Toe board which we'll fill with+alternating X's and O's:  ```haskell data Piece = X | O deriving Show+toPiece :: Int -> Piece toPiece n = if even n then X                       else O 

@@ -0,0 +1,15 @@+module Benchmarks where++import Gauge.Main+import Data.Grid as G++benchTranspose :: forall dims a x y. (Dimensions dims) =>  (dims ~ [x, y]) => Int -> (Grid dims Int, Grid dims Int, Grid dims Int)+benchTranspose a = (transpose $ pure 1, transpose $ pure 2, transpose $ pure 3)++main :: IO ()+main = defaultMain+  [ bgroup+      "permutations"+      [ bench "nf [150, 150]" $ nf (benchTranspose @[200, 200]) 2+      ]+  ]

@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: 21db274f8abd8e6d956d24ef25c4ad5c0c1118727eccae42c59a1db28229edd3+-- hash: b776a0436dd05eb78d384efe21494a96d7c6b28f0de9046d2011ea75f53025df  name:           grids-version:        0.2.0.0+version:        0.3.0.0 description:    Arbitrary sized type-safe grids with useful combinators category:       Data Structures homepage:       https://github.com/ChrisPenner/grids#readme@@ -29,15 +29,72 @@ library   exposed-modules:       Data.Grid-      Data.Grid.Lens+      Data.Grid.Examples.Conway+      Data.Grid.Examples.Intro+      Data.Grid.Internal.Convolution+      Data.Grid.Internal.Coord+      Data.Grid.Internal.Errors+      Data.Grid.Internal.Grid+      Data.Grid.Internal.Identity+      Data.Grid.Internal.Lens+      Data.Grid.Internal.Nest+      Data.Grid.Internal.NestedLists+      Data.Grid.Internal.Pretty+      Data.Grid.Internal.Transpose   other-modules:       Paths_grids   hs-source-dirs:       src+  default-extensions: KindSignatures PolyKinds TypeApplications ScopedTypeVariables TypeOperators TypeFamilies FlexibleInstances FlexibleContexts MultiParamTypeClasses DataKinds GeneralizedNewtypeDeriving DeriveTraversable DeriveFunctor ConstraintKinds+  ghc-options: -fwarn-redundant-constraints   build-depends:       adjunctions     , base >=4.7 && <5+    , comonad+    , deepseq     , distributive-    , finite-typelits+    , singletons+    , vector+  default-language: Haskell2010++test-suite specs+  type: exitcode-stdio-1.0+  main-is: Spec.hs+  other-modules:+      Paths_grids+  hs-source-dirs:+      test+  default-extensions: KindSignatures PolyKinds TypeApplications ScopedTypeVariables TypeOperators TypeFamilies FlexibleInstances FlexibleContexts MultiParamTypeClasses DataKinds GeneralizedNewtypeDeriving DeriveTraversable DeriveFunctor ConstraintKinds+  ghc-options: -threaded -rtsopts -with-rtsopts=-N -main-is Spec+  build-depends:+      adjunctions+    , base >=4.7 && <5+    , comonad+    , deepseq+    , distributive+    , grids+    , hspec+    , singletons+    , vector+  default-language: Haskell2010++benchmark stat+  type: exitcode-stdio-1.0+  main-is: Benchmarks.hs+  other-modules:+      Paths_grids+  hs-source-dirs:+      benchmarks+  default-extensions: KindSignatures PolyKinds TypeApplications ScopedTypeVariables TypeOperators TypeFamilies FlexibleInstances FlexibleContexts MultiParamTypeClasses DataKinds GeneralizedNewtypeDeriving DeriveTraversable DeriveFunctor ConstraintKinds+  ghc-options: -threaded -rtsopts -with-rtsopts=-N -main-is Benchmarks+  build-depends:+      adjunctions+    , base >=4.7 && <5+    , comonad+    , deepseq+    , distributive+    , gauge+    , grids+    , singletons     , vector   default-language: Haskell2010

@@ -1,212 +1,65 @@-{-# LANGUAGE FlexibleContexts #-}-{-# LANGUAGE DeriveTraversable #-}-{-# LANGUAGE GeneralizedNewtypeDeriving #-}-{-# language ScopedTypeVariables #-}-{-# LANGUAGE TypeApplications #-}-{-# LANGUAGE KindSignatures #-}-{-# LANGUAGE PolyKinds #-}-{-# LANGUAGE DataKinds #-}-{-# LANGUAGE TypeFamilies #-}-{-# LANGUAGE MultiParamTypeClasses #-}-{-# LANGUAGE FlexibleInstances #-}-{-# LANGUAGE ConstraintKinds #-}-{-# LANGUAGE TypeInType #-}-{-# LANGUAGE TypeOperators #-}-{-# LANGUAGE UndecidableInstances #-}-{-# LANGUAGE InstanceSigs #-}-{-# LANGUAGE UndecidableSuperClasses #-}-{-# LANGUAGE RankNTypes #-}- module Data.Grid-  ( Grid(..)-  , GridSize-  , Dimensions(..)-  , Coord-  , (:#)(..)-  , NestedLists+  (+  -- * Grids+   Grid(..)+   -- * Creation   , generate-  , toNestedLists+  , Rep.tabulate   , fromNestedLists+  , fromNestedLists'   , fromList-  , (//)-  )-where--import           Data.Distributive-import           Data.Functor.Rep-import qualified Data.Vector                   as V-import           Data.Proxy-import           Data.Kind-import           GHC.TypeNats                  as N-import           Data.Finite-import           Control.Applicative-import           Data.List-import           Data.Bifunctor--toFinite :: (KnownNat n) => Integral m => m -> Finite n-toFinite = finite . fromIntegral--fromFinite :: Num n => Finite m -> n-fromFinite = fromIntegral . getFinite---- | An grid of arbitrary dimensions.------ e.g. a @Grid [2, 3] Int@ might look like:------ > generate id :: Grid [2, 3] Int--- > (Grid [[0,1,2],--- >        [3,4,5]])-newtype Grid (dims :: [Nat]) a =-  Grid  (V.Vector a)-  deriving (Eq, Functor, Foldable, Traversable)--instance (Dimensions dims, Show (NestedLists dims a)) => Show (Grid dims a) where-  show g = "(Grid " ++ show (toNestedLists g) ++ ")"--instance (Dimensions dims, Semigroup a) => Semigroup (Grid dims a) where-  (<>) = liftA2 (<>)--instance (Dimensions dims, Monoid a) => Monoid (Grid dims a) where-  mempty = pure mempty--instance (Dimensions dims) => Applicative (Grid dims) where-  pure a = tabulate (const a)-  liftA2 f (Grid v) (Grid u) = Grid $ V.zipWith f v u---- | Calculate the number of elements in a grid of the given dimensionality-type family GridSize (dims :: [Nat]) :: Nat where-  GridSize '[] = 0-  GridSize (x:'[]) = x-  GridSize (x:xs) = (x N.* GridSize xs)---- | Used for constructing arbitrary depth coordinate lists --- e.g. @('Finite' 2 ':#' 'Finite' 3)@-data x :# y = x :# y-  deriving (Show, Eq, Ord)--infixr 9 :#---- | The coordinate type for a given dimensionality------ > Coord [2, 3] == Finite 2 :# Finite 3--- > Coord [4, 3, 2] == Finite 4 :# Finite 3 :# Finite 2-type family Coord (dims :: [Nat]) where-  Coord '[n] = Finite n-  Coord (n:xs) = Finite n :# Coord xs---- | Represents valid dimensionalities. All non empty lists of Nats have--- instances-class (AllC KnownNat dims, KnownNat (GridSize dims)) => Dimensions (dims :: [Nat]) where-  toCoord :: Proxy dims -> Finite (GridSize dims) -> Coord dims-  fromCoord :: Proxy dims -> Coord dims -> Finite (GridSize dims)-  gridSize-    :: Proxy dims -> Int-  gridSize _ = fromIntegral $ natVal (Proxy @(GridSize dims))-  nestLists :: Proxy dims -> V.Vector a -> NestedLists dims a-  unNestLists :: Proxy dims -> NestedLists dims a -> [a]--type family AllC (c :: x -> Constraint) (ts :: [x]) :: Constraint where-  AllC c '[] = ()-  AllC c (x:xs) = (c x, AllC c xs)--instance (KnownNat x) => Dimensions '[x] where-  toCoord _ i = i-  fromCoord _ i = i-  nestLists _ = V.toList-  unNestLists _ xs = xs+  , fromList' -instance (KnownNat (GridSize (x:y:xs)), KnownNat x, Dimensions (y:xs)) => Dimensions (x:y:xs) where-  toCoord _ n = firstCoord :# toCoord (Proxy @(y:xs)) remainder-    where-      firstCoord = toFinite (n `div` fromIntegral (gridSize (Proxy @(y:xs))))-      remainder = toFinite (fromFinite n `mod` gridSize (Proxy @(y:xs)))-  fromCoord _ (x :# ys) =-    toFinite $ firstPart + rest-      where-        firstPart = fromFinite x * gridSize (Proxy @(y:xs))-        rest = fromFinite (fromCoord (Proxy @(y:xs)) ys)-  nestLists _ v = nestLists (Proxy @(y:xs)) <$> chunkVector (Proxy @(GridSize (y:xs))) v-  unNestLists _ xs = concat (unNestLists (Proxy @(y:xs)) <$> xs)+  -- * Collapsing+  , toNestedLists -instance (Dimensions dims) => Distributive (Grid dims) where-  distribute = distributeRep+  -- * Indexing+  , Coord(..)+  , coord+  , unconsC+  , appendC+  , Rep.index -instance (Dimensions dims) => Representable (Grid dims) where-  type Rep (Grid dims) = Coord dims-  index (Grid v) ind = v V.! fromIntegral (fromCoord (Proxy @dims) ind)-  tabulate f = Grid $ V.generate (fromIntegral $ gridSize (Proxy @dims)) (f . toCoord (Proxy @dims) . fromIntegral)+  -- * Updating+  , (//) --- | Computes the level of nesting requried to represent a given grid--- dimensionality as a nested list------ > NestedLists [2, 3] Int == [[Int]]--- > NestedLists [2, 3, 4] Int == [[[Int]]]-type family NestedLists (dims :: [Nat]) a where-  NestedLists '[] a = a-  NestedLists (_:xs) a = [NestedLists xs a]+  -- * Lenses+  , cell --- | Build a grid by selecting an element for each element-generate :: forall dims a . Dimensions dims => (Int -> a) -> Grid dims a-generate f = Grid $ V.generate (gridSize (Proxy @dims)) f+  -- * Convolution+  , autoConvolute+  , convolute --- | Build a grid by selecting an element for each coordinate-generateCoord-  :: forall dims a . Dimensions dims => (Coord dims -> a) -> Grid dims a-generateCoord f = generate (f . toCoord (Proxy @dims) . fromIntegral)+  -- ** Window restriction+  , clampWindow+  , wrapWindow+  , safeWindow -chunkVector :: forall n a . KnownNat n => Proxy n -> V.Vector a -> [V.Vector a]-chunkVector _ v-  | V.null v-  = []-  | otherwise-  = let (before, after) = V.splitAt (fromIntegral $ natVal (Proxy @n)) v-    in  before : chunkVector (Proxy @n) after+  -- * Permutations+  , transpose+  , permute+  , permuteCoord --- | Turn a grid into a nested list structure. List nesting increases for each--- dimension------ > toNestedLists (G.generate id :: Grid [2, 3] Int)--- > [[0,1,2],[3,4,5]]-toNestedLists-  :: forall dims a . (Dimensions dims) => Grid dims a -> NestedLists dims a-toNestedLists (Grid v) = nestLists (Proxy @dims) v+  -- * Joining+  , joinGrid+  , splitGrid --- | Turn a nested list structure into a Grid if the list is well formed. --- Required list nesting increases for each dimension------ > fromNestedLists [[0,1,2],[3,4,5]] :: Maybe (Grid [2, 3] Int)--- > Just (Grid [[0,1,2],[3,4,5]])--- > fromNestedLists [[0],[1,2]] :: Maybe (Grid [2, 3] Int)--- > Nothing-fromNestedLists-  :: forall dims a-   . Dimensions dims-  => NestedLists dims a-  -> Maybe (Grid dims a)-fromNestedLists = fromList . unNestLists (Proxy @dims)+  -- * Assorted+  , gridSize --- | Convert a list into a Grid or fail if not provided the correct number of--- elements------ > G.fromList [0, 1, 2, 3, 4, 5] :: Maybe (Grid [2, 3] Int)--- > Just (Grid [[0,1,2],[3,4,5]])--- > G.fromList [0, 1, 2, 3] :: Maybe (Grid [2, 3] Int)--- > Nothing-fromList-  :: forall a dims-   . (KnownNat (GridSize dims), Dimensions dims)-  => [a]-  -> Maybe (Grid dims a)-fromList xs =-  let v = V.fromList xs-  in  if V.length v == gridSize (Proxy @dims) then Just $ Grid v else Nothing+  -- * Typeclasses & Type Families+  , Dimensions+  , NestedLists+  , Neighboring+  , ValidPermutation+  , Permuted+  )+where --- | Update elements of a grid-(//)-  :: forall dims a-   . (Dimensions dims)-  => Grid dims a-  -> [(Coord dims, a)]-  -> Grid dims a-(Grid v) // xs =-  Grid (v V.// fmap (first (fromFinite . fromCoord (Proxy @dims))) xs)+import           Data.Grid.Internal.Grid+import           Data.Grid.Internal.Nest+import           Data.Grid.Internal.Lens+import           Data.Grid.Internal.Transpose+import           Data.Grid.Internal.Coord+import           Data.Grid.Internal.Convolution+import           Data.Functor.Rep as Rep

@@ -0,0 +1,34 @@+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE OverloadedLists #-}+module Data.Grid.Examples.Conway where++import Data.Grid+import Data.Foldable+import Data.List++rule :: Grid '[3, 3] Bool -> Bool+rule g = (currentCellAlive && livingNeighbours == 2) || livingNeighbours == 3+ where+  currentCellAlive = g `index` Coord [1, 1] -- Get the center cell+  livingNeighbours =+    (if currentCellAlive then subtract 1 else id) . length . filter id $ toList+      g++step :: (Dimensions dims) => Grid dims Bool -> Grid dims Bool+step = autoConvolute wrapWindow rule++glider :: [Coord '[10, 10]]+glider = Coord <$> [[0, 1], [1, 2], [2, 0], [2, 1], [2, 2]]++start :: Grid '[10, 10] Bool+start = tabulate (`elem` glider)++simulate :: Int -> Grid '[10, 10] Bool+simulate = (iterate step start !!)++showBool :: Bool -> Char+showBool True  = '#'+showBool False = '.'++showGrid :: (Dimensions '[x, y]) => Grid '[x, y] Bool -> String+showGrid = intercalate "\n" . toNestedLists . fmap showBool

@@ -0,0 +1,71 @@+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeApplications #-}+module Data.Grid.Examples.Intro where++import Data.Grid+import Data.Maybe+import Data.Functor.Compose+import Data.Coerce+import Data.Foldable+import Data.Functor.Rep+import GHC.TypeNats hiding ()++simpleGrid :: Grid '[5, 5] Int+simpleGrid = generate id++coordGrid :: Grid '[5, 5] (Coord '[5, 5])+coordGrid = tabulate id+++avg :: Foldable f => f Int -> Int+avg f | null f    = 0+      | otherwise = sum f `div` length f++mx :: Foldable f => f Int -> Int+mx = maximum++small :: Grid '[3, 3] Int+small = generate id++small' :: Grid '[5, 5] Int+small' = generate id+++med :: Grid '[3, 3, 3] Int+med = generate id++big :: Grid '[5, 5, 5, 5] Int+big = generate id++gauss :: (Dimensions dims) => Grid dims Double -> Grid dims Double+gauss = autoConvolute safeWindow gauss'+ where+  gauss' :: Compose (Grid '[3, 3]) Maybe Double -> Double+  gauss' g = (sum g) / fromIntegral (length g)++clampGauss :: (Dimensions dims) => Grid dims Double -> Grid dims Double+clampGauss = autoConvolute clampWindow gauss'+ where+  gauss' :: Grid '[3, 3] Double -> Double+  gauss' g = sum g / fromIntegral (length g)+++seeNeighboring :: Grid '[3, 3] a -> Grid '[3, 3] (Grid '[3, 3] (Maybe a))+seeNeighboring = autoConvolute safeWindow go+ where+  go :: Compose (Grid '[3, 3]) Maybe a -> Grid '[3, 3] (Maybe a)+  go = getCompose . coerce++coords :: Grid '[3, 3] (Coord '[3, 3])+coords = tabulate id++doubleGrid :: Grid '[3, 3] Double+doubleGrid = fromIntegral <$> small++simpleGauss :: Grid '[3, 3] Double+simpleGauss = gauss doubleGrid++pacmanGauss :: (Dimensions dims) => Grid dims Double -> Grid dims Double+pacmanGauss = autoConvolute @'[3, 3] wrapWindow gauss'+  where gauss' g = sum g / fromIntegral (length g)

@@ -0,0 +1,158 @@+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE AllowAmbiguousTypes #-}+module Data.Grid.Internal.Convolution where++import           Data.Grid.Internal.Grid+import           Data.Grid.Internal.Coord+import           Data.Grid.Internal.Nest+import           Data.Functor.Rep+import           GHC.TypeNats+import           Data.Kind+import           Control.Applicative+import           Data.Functor.Compose+import           Data.Foldable+import           Data.Coerce++import           Control.Comonad+import           Control.Comonad.Representable.Store+import           Data.Maybe+import           Data.Proxy++criticalError :: a+criticalError = error+  "Something went wrong, please report this issue to the maintainer of grids"++-- | Perform a computation based on the context surrounding a cell+-- Good for doing things like Linear Image Filters (e.g. gaussian blur) or+-- simulating Cellular Automata (e.g. Conway's game of life)+--+-- This function accepts a function which indicates what to do with+-- 'out-of-bounds' indexes, 'clampWindow', 'wrapWindow' and 'safeWindow'+-- are examples.+--+-- It also acccepts a transformation function which operates over the+-- functor created by the first parameter and collapses it down to a new+-- value for the cell at that position.+--+-- This function is best used with Type Applications to denote the desired+-- window size; the Grid passed to the given function contains the current cell+-- (in the middle) and all the surrounding cells.+--+-- Here's an example of computing the average of all neighbouring cells,+-- repeating values at the edge of the grid when indexes are out of bounds+-- (using 'clampWindow')+--+-- > gaussian :: (Dimensions dims) => Grid dims Double -> Grid dims Double+-- > gaussian = autoConvolute clampWindow avg+-- >  where+-- >   avg :: Grid '[3, 3] Double -> Double+-- >   avg g = sum g / fromIntegral (length g)+autoConvolute+  :: forall window dims f a b+   . ( Dimensions dims+     , Dimensions window+     , Functor f+     , Neighboring window+     )+  => (Grid window (Coord dims) -> f (Coord dims)) -- ^ Restrict out of bounds coordinates in some way. Use 'clampWindow', 'wrapWindow' or 'safeWindow'+  -> (f a -> b) -- ^ Collapse the context down to a value+  -> Grid dims a -- ^ Starting grid+  -> Grid dims b+autoConvolute restrict = convolute (restrict . window @window @dims)++-- | This is a fully generic version of 'autoConvolute' which allows+-- the user to provide a function which builds a context from the current+-- coord, then provides a collapsing function over the same functor.+convolute+  :: forall dims f a b+   . (Functor f, Dimensions dims)+  => (Coord dims -> f (Coord dims))  -- ^ Build a neighbouring context within a functor from the current coord+  -> (f a -> b) -- ^ Collapse the context to a single value+  -> Grid dims a -- ^ Starting grid+  -> Grid dims b+convolute selectWindow f g =+  let s = store (index g) criticalError+      convoluted :: Store (Grid dims) b+      convoluted     = extend (f . experiment (fmap roundTrip . selectWindow)) s+      (tabulator, _) = runStore convoluted+  in  tabulate tabulator+ where+  roundTrip :: Coord dims -> Coord dims+  roundTrip = toEnum . fromEnum++-- | Given a coordinate generate a grid of size 'window' filled with+-- coordinates surrounding the given coord. Mostly used internally+window+  :: forall window dims+   . (Neighboring window, Dimensions window)+  => Coord dims+  -> Grid window (Coord dims)+window = fromWindow . neighboring . toWindow+ where+  toWindow :: Coord dims -> Coord window+  toWindow = coerceCoordDims+  fromWindow :: Grid window (Coord window) -> Grid window (Coord dims)+  fromWindow = fmap coerceCoordDims++-- data Orth a =+--   Orth+--     { up :: a+--     , right :: a+--     , down :: a+--     , left :: a+--     } deriving (Eq, Show, Functor, Traversable, Foldable)++-- orthNeighbours :: Coord dims  -> Compose Orth Maybe (Coord dims )+-- orthNeighbours c = Compose+--   (   toMaybe+--   <$> traverse+--         (+)+--         Orth {up = 0 :# (-1), right = 1 :# 0, down = 0 :# 1, left = -1 :# 0}+--         c+--   )+--  where+--   toMaybe c@(x :# y) | not (inBounds x) || not (inBounds y) = Nothing+--                      | otherwise                            = Just c++-- orthFromList [up', right', down', left'] =+--   Orth {up = up, right = right', down = down', left = left'}++class Neighboring dims where+  neighbors :: Grid dims (Coord dims)++instance {-# OVERLAPPING #-} (KnownNat n) => Neighboring '[n]  where+  neighbors = fromList' . fmap (Coord . pure . subtract (numVals `div` 2)) . take numVals $ [0 .. ]+    where+      numVals = gridSize @'[n]++instance (KnownNat n, Neighboring ns) => Neighboring (n:ns) where+  neighbors = joinGrid (addCoord <$> currentLevelNeighbors)+    where+      addCoord :: Coord '[n]  -> Grid ns (Coord (n : ns) )+      addCoord c = appendC c <$> nestedNeighbors+      nestedNeighbors :: Grid ns (Coord ns )+      nestedNeighbors = neighbors+      currentLevelNeighbors :: Grid '[n] (Coord '[n] )+      currentLevelNeighbors = neighbors++neighboring :: (Dimensions dims, Neighboring dims) => Coord dims -> Grid dims (Coord dims)+neighboring c = (c +) <$> neighbors++-- | Use with 'autoConvolute'; Clamp out-of-bounds coordinates to the nearest in-bounds coord.+clampWindow+  :: (Dimensions dims) => Grid window (Coord dims) -> Grid window (Coord dims)+clampWindow = fmap clampCoord++-- | Use with 'autoConvolute'; Wrap out-of-bounds coordinates pac-man style to the other side of the grid+wrapWindow+  :: (Dimensions dims) => Grid window (Coord dims) -> Grid window (Coord dims)+wrapWindow = fmap wrapCoord++-- | Use with 'autoConvolute'; Out of bounds coords become 'Nothing'+safeWindow+  :: (Dimensions dims) => Grid window (Coord dims) -> Compose (Grid window) Maybe (Coord dims)+safeWindow = Compose . fmap wrap+  where+    wrap c | coordInBounds c = Just c+           | otherwise  = Nothing

@@ -0,0 +1,123 @@+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE MultiParamTypeClasses #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE TypeOperators #-}+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE TypeFamilyDependencies #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE ConstraintKinds #-}+{-# LANGUAGE GADTs #-}+{-# LANGUAGE AllowAmbiguousTypes #-}+{-# LANGUAGE StandaloneDeriving #-}+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE ViewPatterns #-}++module Data.Grid.Internal.Coord where++import           GHC.Exts+import           GHC.TypeNats                      hiding ( Mod )+import           GHC.TypeLits hiding (natVal, Mod)+import           Data.Proxy+import           Data.Kind+import           Unsafe.Coerce+import           Data.Coerce+import           Data.List+import           Data.Singletons.Prelude++-- | The index type for 'Grid's.+newtype Coord (dims :: [Nat]) = Coord {unCoord :: [Int]}+  deriving (Eq)++-- | Safely construct a 'Coord' for a given grid size, checking that all+-- indexes are in range+--+-- > λ> coord @[3, 3] [1, 2]+-- > Just [1, 2]+-- >+-- > λ> coord @[3, 3] [3, 3]+-- > Nothing+-- >+-- > λ> coord @[3, 3] [1, 2, 3]+-- > Nothing+coord :: forall dims. SingI dims => [Int] -> Maybe (Coord dims)+coord ds = if inRange && correctLength then Just (Coord ds)+                      else Nothing+  where+    inRange = all (>=0) ds && all id (zipWith (<) ds (fromIntegral <$> demote @dims))+    correctLength = length ds == length (demote @dims)++instance IsList (Coord dims) where+  type Item (Coord dims) = Int+  fromList = coerce+  toList = coerce++instance Show (Coord dims)+  where+    show (Coord cs) = "[" ++ intercalate ", " (show <$> cs) ++ "]"++-- | Get the first index from a 'Coord'+unconsC :: Coord (n : ns) -> (Int, Coord ns)+unconsC (Coord (n : ns)) = (n, Coord ns)++-- | Append two 'Coord's+appendC :: Coord ns -> Coord ms -> Coord (ns ++ ms) +appendC (Coord ns) (Coord ms) = Coord (ns ++ ms)++pattern (:#) :: Int -> Coord ns -> Coord (n:ns) +pattern n :# ns <- (unconsC -> (n, ns)) where+  n :# (unCoord -> ns) = Coord (n:ns)++instance (Enum (Coord ns)) => Num (Coord ns ) where+  (Coord xs) + (Coord ys) = Coord (zipWith (+) xs ys)+  a - b = a + (negate b)+  (Coord xs) * (Coord ys) = Coord (zipWith (*) xs ys)+  abs (Coord xs) = Coord (abs <$> xs)+  signum (Coord xs) = Coord (signum <$> xs)+  fromInteger = toEnum . fromIntegral+  negate (Coord xs) = Coord (negate <$> xs)++highestIndex :: forall n. KnownNat n => Int+highestIndex = fromIntegral $ natVal (Proxy @n) - 1++clamp :: Int -> Int -> Int -> Int+clamp start end = max start . min end++clampCoord :: forall dims. SingI dims => Coord dims -> Coord dims+clampCoord (Coord ns) = Coord (zipWith (clamp 0 . fromIntegral) (demote @dims) ns)++wrapCoord :: forall dims. SingI dims => Coord dims -> Coord dims+wrapCoord (Coord ns) = Coord (zipWith mod  ns (fromIntegral <$> demote @dims)) ++instance Bounded (Coord '[] ) where+  minBound = Coord []+  maxBound = Coord []++instance (KnownNat n, Bounded (Coord ns )) => Bounded (Coord (n:ns) ) where+  minBound = 0 :# minBound+  maxBound = highestIndex @n :# maxBound++instance  (KnownNat n) => Enum (Coord '[n]) where+  toEnum i = Coord [i]+  fromEnum (Coord [i]) = clamp 0 (highestIndex @n) i++instance  (KnownNat x, KnownNat y, SingI rest, Bounded (Coord rest ), Enum (Coord (y:rest) )) => Enum (Coord (x:y:rest) ) where+  toEnum i | i < 0 = negate $ toEnum (abs i)+  toEnum i | i > fromEnum (maxBound @(Coord (x:y:rest) )) = error "Index out of bounds"+  toEnum i = (i `div` (gridSize @(y:rest))) :# toEnum (i `mod` gridSize @(y:rest))+  fromEnum (x :# ys) = (clamp 0 (highestIndex @x) x * gridSize @(y:rest)) + fromEnum ys++-- | Get the total size of a 'Grid' of the given dimensions+--+-- > gridSize @'[2, 2] == 4+gridSize :: forall (dims :: [Nat]) . SingI dims => Int+gridSize = product . fmap fromIntegral $ demote @dims++coerceCoordDims :: Coord ns -> Coord ms+coerceCoordDims = unsafeCoerce++coordInBounds :: forall ns. (SingI ns) => Coord ns -> Bool+coordInBounds (Coord cs) = all inRange $ zip cs maxIndexes+  where+    maxIndexes = fromIntegral <$> demote @ns+    inRange (val,upperBound) = val >= 0 && val < upperBound

@@ -0,0 +1,11 @@+{-# LANGUAGE UndecidableInstances #-}+module Data.Grid.Internal.Errors where++import Data.Kind+import GHC.TypeLits++type family (b :: Bool) ?! (e :: ErrorMessage) :: Constraint where+  True ?! _ = ()+  False ?! e = TypeError e++infixr 1 ?!

@@ -0,0 +1,124 @@+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE UndecidableSuperClasses #-}+{-# LANGUAGE AllowAmbiguousTypes #-}++module Data.Grid.Internal.Grid+  ( Grid(..)+  , Dimensions(..)+  , Coord+  , NestedLists+  , generate+  , toNestedLists+  , fromNestedLists+  , fromNestedLists'+  , fromList+  , fromList'+  , (//)+  )+where++import           Data.Grid.Internal.NestedLists+import           Data.Grid.Internal.Coord+import           Data.Grid.Internal.Pretty+import           Data.Distributive+import           Data.Functor.Rep+import qualified Data.Vector                   as V+import           Data.Proxy+import           Data.Kind+import           GHC.TypeNats                  as N+                                                   hiding ( Mod )+import           Control.Applicative+import           Data.List+import           Data.Bifunctor+import           Data.Maybe+import           Data.Singletons.Prelude+import           Control.DeepSeq++-- | An grid of arbitrary dimensions.+--+-- e.g. a @Grid [2, 3] Int@ might look like:+--+-- > generate id :: Grid [2, 3] Int+-- > fromNestedLists [[0,1,2],+-- >                  [3,4,5]]+newtype Grid (dims :: [Nat]) a =+  Grid  {toVector :: V.Vector a}+  deriving (Eq, Functor, Foldable, Traversable, NFData)++instance (PrettyList (NestedLists dims a), Dimensions dims, Show (NestedLists dims a)) => Show (Grid dims a) where+  show g = "fromNestedLists \n" ++ (unlines . fmap ("  " ++ ) . lines $ prettyList (toNestedLists g))++instance (Dimensions dims, Semigroup a) => Semigroup (Grid dims a) where+  (<>) = liftA2 (<>)++instance (Dimensions dims, Monoid a) => Monoid (Grid dims a) where+  mempty = pure mempty++instance (Dimensions dims) => Applicative (Grid dims) where+  pure a = tabulate (const a)+  liftA2 f (Grid v) (Grid u) = Grid $ V.zipWith f v u++instance (Dimensions dims) => Distributive (Grid dims) where+  distribute = distributeRep++instance (Dimensions dims) => Representable (Grid dims) where+  type Rep (Grid dims) = Coord dims+  index (Grid v) c = v V.! fromEnum c+  tabulate f = Grid $ V.generate (fromIntegral $ gridSize @dims) (f . toEnum  . fromIntegral)++-- | Build a grid by selecting an element for each element+generate :: forall dims a . (SingI dims) => (Int -> a) -> Grid dims a+generate f = Grid $ V.generate (gridSize @dims) f++-- | Turn a grid into a nested list structure. List nesting increases for each+-- dimension+--+-- > toNestedLists (G.generate id :: Grid [2, 3] Int)+-- > [[0,1,2],[3,4,5]]+toNestedLists+  :: forall dims a . (Dimensions dims) => Grid dims a -> NestedLists dims a+toNestedLists (Grid v) = nestLists (Proxy @dims) v++-- | Turn a nested list structure into a Grid if the list is well formed. +-- Required list nesting increases for each dimension+--+-- > fromNestedLists [[0,1,2],[3,4,5]] :: Maybe (Grid [2, 3] Int)+-- > Just (Grid [[0,1,2],[3,4,5]])+-- > fromNestedLists [[0],[1,2]] :: Maybe (Grid [2, 3] Int)+-- > Nothing+fromNestedLists+  :: forall dims a+   . Dimensions dims+  => NestedLists dims a+  -> Maybe (Grid dims a)+fromNestedLists = fromList . unNestLists (Proxy @dims)++-- | Partial variant of 'fromNestedLists' which errors on malformed input+fromNestedLists'+  :: forall dims a . Dimensions dims => NestedLists dims a -> Grid dims a+fromNestedLists' = fromJust . fromNestedLists++-- | Convert a list into a Grid or fail if not provided the correct number of+-- elements+--+-- > G.fromList [0, 1, 2, 3, 4, 5] :: Maybe (Grid [2, 3] Int)+-- > Just (Grid [[0,1,2],[3,4,5]])+-- > G.fromList [0, 1, 2, 3] :: Maybe (Grid [2, 3] Int)+-- > Nothing+fromList :: forall dims a . (SingI dims) => [a] -> Maybe (Grid dims a)+fromList xs =+  let v = V.fromList xs+  in  if V.length v == gridSize @dims then Just $ Grid v else Nothing++-- | Partial variant of 'fromList' which errors on malformed input+fromList' :: forall dims a . (SingI dims) => [a] -> Grid dims a+fromList' = fromJust . fromList++-- | Update elements of a grid+(//)+  :: forall dims a+   . (Enum (Coord dims ))+  => Grid dims a+  -> [(Coord dims , a)]+  -> Grid dims a+(Grid v) // xs = Grid (v V.// fmap (first fromEnum) xs)

@@ -0,0 +1,18 @@+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE PolyKinds #-}+module Data.Grid.Internal.Identity where++import Data.Grid.Internal.Grid+import Data.Vector as V+import Data.Proxy+import GHC.TypeNats++-- idMatrix+--   :: forall (n :: Nat) (ns :: [Nat]) ind x+--    . (Num x, Dimensions (n : ns), Dimensions ns)+--   => Grid (n : ns) x+-- idMatrix = Grid ns+--  where+--   ns = V.generate (inhabitants @(n : ns)) thing+--   thing n = if n `mod` (inhabitants @ns + 1) == 0 then 1 else 0

@@ -0,0 +1,27 @@+{-# LANGUAGE RankNTypes #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# LANGUAGE FlexibleContexts #-}+module Data.Grid.Internal.Lens where++import Data.Grid.Internal.Grid+import Data.Functor.Rep as R+import Data.Vector as V+import Data.Proxy++type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t+type Lens' s a  = Lens s s a a++lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b+lens sa sbt afb s = sbt s <$> afb (sa s)++-- | Focus an element of a 'Grid' given its 'Coord'+cell+  :: forall ind dims a+   . (Dimensions dims)+  => Coord dims+  -> Lens' (Grid dims a) a+cell c = lens get set+ where+  get          = flip R.index c+  vectorOffset = fromEnum c+  set (Grid v) new = Grid (v V.// [(vectorOffset, new)])

@@ -0,0 +1,40 @@+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE ScopedTypeVariables #-}+{-# OPTIONS_GHC -fno-warn-redundant-constraints #-}+module Data.Grid.Internal.Nest where++import Data.Grid.Internal.Grid+import Data.Grid.Internal.Coord+import Data.Singletons.Prelude+import Data.Maybe+++-- | The inverse of 'splitGrid', +-- joinGrid will nest a grid from:+-- > Grid outer (Grid inner a) -> Grid (outer ++ inner) a+--+-- For example, you can nest a simple 3x3 from smaller [3] grids as follows:+--+-- > joinGrid (myGrid :: Grid [3] (Grid [3] a)) :: Grid '[3, 3] a+joinGrid :: Grid dims (Grid ns a) -> Grid (dims ++ ns) a+joinGrid (Grid v) = Grid (v >>= toVector)++-- | The inverse of 'joinGrid', +-- splitGrid @outerDims @innerDims will un-nest a grid from:+-- > Grid (outer ++ inner) a -> Grid outer (Grid inner a)+--+-- For example, you can unnest a simple 3x3 as follows:+--+-- > splitGrid @'[3] @'[3] myGrid :: Grid '[3] (Grid [3] a)+splitGrid+  :: forall outer inner a from+   . ( from ~ (outer ++ inner)+     , Dimensions from+     , Dimensions inner+     , Dimensions outer+     , NestedLists from a ~ NestedLists outer (NestedLists inner a)+     )+  => Grid from a+  -> Grid outer (Grid inner a)+splitGrid = fmap fromNestedLists' . fromNestedLists' . toNestedLists

@@ -0,0 +1,45 @@+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE UndecidableSuperClasses #-}+module Data.Grid.Internal.NestedLists where++import           Data.Kind+import           GHC.TypeNats                  as N+import           Data.Singletons.Prelude+import qualified Data.Vector                   as V+import           Data.List+import           Data.Grid.Internal.Coord++type family AllC (c :: x -> Constraint) (ts :: [x]) :: Constraint where+  AllC c '[] = ()+  AllC c (x:xs) = (c x, AllC c xs)++-- | Computes the level of nesting requried to represent a given grid+-- dimensionality as a nested list+--+-- > NestedLists [2, 3] Int == [[Int]]+-- > NestedLists [2, 3, 4] Int == [[[Int]]]+type family NestedLists (dims :: [Nat]) a where+  NestedLists '[] a = a+  NestedLists (_:xs) a = [NestedLists xs a]++chunkVector :: forall a . Int -> V.Vector a -> [V.Vector a]+chunkVector n v+  | V.null v+  = []+  | otherwise+  = let (before, after) = V.splitAt n v in before : chunkVector n after+++-- | Represents valid dimensionalities. All non empty lists of Nats have+-- an instance+class (AllC KnownNat dims, SingI dims, Enum (Coord dims), Bounded (Coord dims)) => Dimensions  (dims :: [Nat]) where+  nestLists :: Proxy dims -> V.Vector a -> NestedLists dims a+  unNestLists :: Proxy dims -> NestedLists dims a -> [a]++instance (KnownNat x) => Dimensions '[x] where+  nestLists _ = V.toList+  unNestLists _ xs = xs++instance (KnownNat x, Bounded (Coord xs), SingI xs, Dimensions (y:xs)) => Dimensions (x:y:xs) where+  nestLists _ v = nestLists (Proxy @(y:xs)) <$> chunkVector (gridSize @(y:xs)) v+  unNestLists _ xs = concat (unNestLists (Proxy @(y:xs)) <$> xs)

@@ -0,0 +1,18 @@+module Data.Grid.Internal.Pretty where++import Data.List++class PrettyList l where+  prettyList :: l -> String++instance {-# OVERLAPPABLE #-} (Show a) => PrettyList [a] where+  prettyList = show++instance {-# OVERLAPPABLE #-} (Show a) => PrettyList [[a]] where+  prettyList ls = "[" ++ intercalate "\n," (prettyList <$> ls) ++ "]"++instance (Show a) => PrettyList [[[ a ]]] where+  prettyList ls = "[" ++ intercalate "\n\n," (unlines . overRest (" " ++ ) . lines . prettyList <$> ls) ++ "]"+    where+      overRest f (l:ls) = l : fmap f ls+      overRest f ls = ls

@@ -0,0 +1,98 @@+{-# LANGUAGE AllowAmbiguousTypes #-}+{-# LANGUAGE UndecidableInstances #-}+{-# LANGUAGE FunctionalDependencies #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE PolyKinds #-}+{-# OPTIONS_GHC -fno-warn-redundant-constraints #-}+module Data.Grid.Internal.Transpose where++import           Data.Grid.Internal.Grid+import           Data.Grid.Internal.Errors+import           Data.Grid.Internal.Coord+import           GHC.TypeNats+import           GHC.TypeLits                  as TL+import           Data.Singletons.Prelude+import           Data.Singletons.Prelude.List  as L+import           Data.Singletons.Prelude.Maybe+import           Data.Functor.Rep+import           Data.Vector                   as V+import           Data.Kind+import           Data.Maybe+import           Data.List++type family Permuted (key :: [Nat]) (from :: [Nat]) :: [Nat] where+  Permuted '[] _ = '[]+  Permuted (x:xs) from = (from !! x) : Permuted xs from++type ValidPermutation key from =+  (Sort key == EnumFromTo 0 (Length from TL.- 1)) ?!+    (Text "Malformed permutation hint: " :<>: ShowType key+                :$$: Text "When permuting matrix of size: " :<>: ShowType from+                :$$: Text "Key must be a permutation of "  :<>: ShowType (EnumFromTo 0 (Length from TL.- 1))+                :$$: Text "e.g. the identity permutation for 2x2 is @[0, 1]"+                :$$: Text "e.g. matrix transpose for 2x2 is @[1, 0]"+  )++-- | Permute dimensions of a 'Grid'. This is similar to MatLab's permute+-- function+--+-- 'permute' requires a type application containing a permutation pattern;+-- The pattern is a re-ordering of the list @[0..n]@ which represents the new+-- dimension order. For example the permutation pattern @[1, 2, 0]@ when+-- applied to the dimensions @[4, 5, 6]@ results in the dimensions @[5, 6, 4]@.+--+-- For 2 dimensional matrixes, a permutation using @[1, 0]@ is simply a +-- matrix 'transpose'+--+-- > λ> small+-- > fromNestedLists+-- >   [[0,1,2]+-- >   ,[3,4,5]+-- >   ,[6,7,8]]+-- >+-- > λ> permute @[1, 0] small+-- > fromNestedLists+-- >   [[0,3,6]+-- >   ,[1,4,7]+-- >   ,[2,5,8]]+permute+  :: forall (key :: [Nat]) from a invertedKey+   . ( SingI invertedKey+     , invertedKey ~ InvertKey (EnumFromTo 0 (Length from TL.- 1)) key+     , ValidPermutation key from+     , Dimensions from +     , Dimensions (Permuted key from) +     )+  => Grid from a+  -> Grid (Permuted key from) a+permute (Grid v) = result+ where+  len = V.length v+  result :: Grid (Permuted key from) a+  result = tabulate+    ((v V.!) . fromEnum  . permuteCoord @invertedKey @from)++-- | Permute the dimensions of a coordinate according to a permutation pattern.+-- see 'permute' regarding permutation patterns+permuteCoord+  :: forall (key :: [Nat]) to from +   . (SingI key)+  => Coord from +  -> Coord to +permuteCoord (Coord cs) = Coord newCoord+ where+  key :: [Int]+  key = fromIntegral <$> demote @key+  newCoord :: [Int]+  newCoord = (cs !!) <$> key++-- | Transpose a 2 dimensional matrix. Equivalent to:+--+-- > permute @[1, 0]+transpose :: (KnownNat x, KnownNat y) => Grid '[x, y] a -> Grid '[y, x] a+transpose = permute @'[1, 0]++-- | Get the inverse of a permutation pattern, used internally+type family InvertKey ref key :: [Nat] where+  InvertKey '[] xs = '[]+  InvertKey (n:ns) xs = FromJust (ElemIndex n xs) : InvertKey ns xs

@@ -1,28 +0,0 @@-{-# LANGUAGE RankNTypes #-}-{-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE TypeApplications #-}-{-# LANGUAGE FlexibleContexts #-}-module Data.Grid.Lens (cell) where--import Data.Grid-import Data.Functor.Rep as R-import Data.Vector as V-import Data.Proxy--type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t-type Lens' s a  = Lens s s a a--lens :: (s -> a) -> (s -> b -> t) -> Lens s t a b-lens sa sbt afb s = sbt s <$> afb (sa s)---- | Focus an element of a grid-cell-  :: forall dims a-   . (Dimensions dims, Eq (Coord dims))-  => Coord dims-  -> Lens' (Grid dims a) a-cell c = lens get set- where-  get          = flip R.index c-  vectorOffset = fromIntegral (fromCoord (Proxy @dims) c)-  set (Grid v) new = Grid (v V.// [(vectorOffset, new)])

@@ -0,0 +1,126 @@+{-# LANGUAGE OverloadedLists #-}+{-# LANGUAGE TypeApplications #-}+module Spec where++import Test.Hspec+import qualified Data.Vector as V+import Data.Grid as G+import Control.Applicative+import Data.Maybe+import Data.Functor.Compose+++smallGrid :: Grid '[2, 2] Int+smallGrid = G.generate id++medGrid :: Grid '[3, 3] Int+medGrid = G.generate id++dim3Grid :: Grid '[2, 3, 4] Int+dim3Grid = G.generate id+++++main :: IO ()+main = hspec $ do+  describe "creation" $ do+    it "pure should make a grid of all one element" $ do+      let Grid v = pure 1 :: Grid '[2, 2] Int+      v `shouldBe` V.replicate 4 1++    it "generate should put things in the right places" $ do+      let g        = G.generate id :: Grid '[2, 2] Int+          expected = fromNestedLists [[0, 1], [2, 3]]+      Just g `shouldBe` expected++    it "tabulate should put coords in the right places" $ do+      let g        = tabulate id :: Grid '[2, 2] (Coord '[2, 2])+          expected = fromNestedLists+            [[Coord [0, 0], Coord [0, 1]], [Coord [1, 0], Coord [1, 1]]]+      Just g `shouldBe` expected++  describe "indexing" $ do+    it "index should retrieve correct elem" $ do+      (smallGrid `index` Coord [0, 0]) `shouldBe` 0+      (smallGrid `index` Coord [0, 1]) `shouldBe` 1+      (smallGrid `index` Coord [1, 0]) `shouldBe` 2+      (smallGrid `index` Coord [1, 1]) `shouldBe` 3++  describe "applicative" $ do+    it "should apply piecewise" $ do+      let expected = fromJust . fromNestedLists $ [[0, 2], [4, 6]]+      liftA2 (+) smallGrid smallGrid `shouldBe` expected++  describe "nested lists" $ do+    it "toNestedLists" $ toNestedLists smallGrid `shouldBe` [[0, 1], [2, 3]]+    it "fromNestedLists"+      $          fromNestedLists [[0, 1], [2, 3]]+      `shouldBe` Just smallGrid+    it "fromList" $ do+      G.fromList [0, 1, 2, 3] `shouldBe` Just smallGrid++  describe "updates" $ do+    it "(//)"+      $          (    smallGrid+                 G.// [(Coord [1, 1] :: Coord '[2, 2], 42), (Coord [0, 1], 100)]+                 )+      `shouldBe` fromNestedLists' [[0, 100], [2, 42]]++  describe "permutations" $ do+    it "transpose" $ do+      transpose smallGrid `shouldBe` fromNestedLists' [[0, 2], [1, 3]]+      transpose medGrid+        `shouldBe` fromNestedLists' [[0, 3, 6], [1, 4, 7], [2, 5, 8]]+    it "permute" $ do+      permute @'[1, 2, 0] dim3Grid `shouldBe` fromNestedLists'+        [ [[0, 12], [1, 13], [2, 14], [3, 15]]+        , [[4, 16], [5, 17], [6, 18], [7, 19]]+        , [[8, 20], [9, 21], [10, 22], [11, 23]]+        ]++  describe "convolutions" $ do+    it "autoConvolute with Clamp clamps out of bounds" $ do+      autoConvolute @'[3, 3] clampWindow toNestedLists smallGrid+        `shouldBe` fromNestedLists'+                     [ [ [[0, 0, 1], [0, 0, 1], [2, 2, 3]]+                       , [[0, 1, 1], [0, 1, 1], [2, 3, 3]]+                       ]+                     , [ [[0, 0, 1], [2, 2, 3], [2, 2, 3]]+                       , [[0, 1, 1], [2, 3, 3], [2, 3, 3]]+                       ]+                     ]++    it "autoConvolute with Mod wraps when out of bounds" $ do+      autoConvolute @'[3, 3] wrapWindow toNestedLists smallGrid+        `shouldBe` fromNestedLists'+                     [ [ [[3, 2, 3], [1, 0, 1], [3, 2, 3]]+                       , [[2, 3, 2], [0, 1, 0], [2, 3, 2]]+                       ]+                     , [ [[1, 0, 1], [3, 2, 3], [1, 0, 1]]+                       , [[0, 1, 0], [2, 3, 2], [0, 1, 0]]+                       ]+                     ]++    it "safeAutoConvolute gets 'Nothing' for out of bounds" $ do+      safeAutoConvolute @'[3, 3] toNestedLists smallGrid+        `shouldBe` fromNestedLists'+                     [ [ [ [Nothing, Nothing, Nothing]+                         , [Nothing, Just 0, Just 1]+                         , [Nothing, Just 2, Just 3]+                         ]+                       , [ [Nothing, Nothing, Nothing]+                         , [Just 0, Just 1, Nothing]+                         , [Just 2, Just 3, Nothing]+                         ]+                       ]+                     , [ [ [Nothing, Just 0, Just 1]+                         , [Nothing, Just 2, Just 3]+                         , [Nothing, Nothing, Nothing]+                         ]+                       , [ [Just 0, Just 1, Nothing]+                         , [Just 2, Just 3, Nothing]+                         , [Nothing, Nothing, Nothing]+                         ]+                       ]+                     ]