grids 0.5.0.0 → 0.5.0.1

raw patch · 4 files changed

+204/−26 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• README.md +10/−5
• benchmarks/Benchmarks.hs +30/−8
• grids.cabal +2/−2
• src/Data/Grid/Examples/Conway.hs +162/−11

@@ -22,8 +22,6 @@  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.@@ -91,7 +89,6 @@ `Coord` is really just a wrapping over a list of integers. It's recommended that you use `coord` to safely construct `Coord` values, but you can cheat and use  the `Coord` constructor or even `OverLoadedLists` if you want to.- Here's the type of Coord for a few different Grids:  You can get a value out of a grid for a particular index out using `index` from `Data.Functor.Rep`: @@ -115,13 +112,14 @@ λ> g ^. cell (Coord [0, 1]) 1 λ> g & cell (Coord [0, 1]) *~ 1000-(Grid [[0,1000,2],[3,4,5]])+(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`). Or of course you can just use `pure`+a function over the coordinate position of the cell (`tabulate`). Or of course you can just use `pure`.  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.@@ -138,3 +136,10 @@ For batch updates using the underlying Vector implementation use `(//)`  - `(//) :: Grid dims a -> [(Coord dims, a)] -> Grid dims a`++## Cellular Automata+See the [haddock docs](http://hackage.haskell.org/package/grids/docs/Data-Grid-Examples-Conway.html) +for a guide on building Conway's game of life in only a few lines.++## Convolution+Coming soon

@@ -1,15 +1,37 @@+{-# LANGUAGE PolyKinds #-}+{-# LANGUAGE AllowAmbiguousTypes #-} module Benchmarks where  import Gauge.Main import Data.Grid as G+import Data.Functor.Compose -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)+benchGauss :: forall window dims x y.+           (IsGrid dims, IsGrid window, dims ~ [x, y])+           => Grid dims Double+           -> Grid dims Double+benchGauss = gauss @window +idGrid :: IsGrid dims => Grid dims Int+idGrid = generate id++gauss :: forall window dims. (IsGrid dims, IsGrid window) => Grid dims Double -> Grid dims Double+gauss = autoConvolute omitBounds gauss'+  where+    gauss' :: Compose (Grid window) Maybe Double -> Double+    gauss' g = (sum g) / fromIntegral (length g)++ main :: IO ()-main = defaultMain-  [ bgroup-      "permutations"-      [ bench "nf [150, 150]" $ nf (benchTranspose @[200, 200]) 2-      ]-  ]+main =+  defaultMain [ bgroup "convolution"+                       [ bgroup "gauss"+                                [ bench "nf [3, 3] window over [100, 100]"+                                    $ nf (benchGauss @[3, 3]) (fromIntegral <$> idGrid @[100, 100])+                                , bench "nf [10, 10] window over [100, 100]"+                                    $ nf (benchGauss @[10, 10]) (fromIntegral <$> idGrid @[100, 100])+                                , bench "nf [3, 3] window over [500, 500]"+                                    $ nf (benchGauss @[3, 3]) (fromIntegral <$> idGrid @[500, 500])+                                ]+                       ]+              ]

@@ -4,10 +4,10 @@ -- -- see: https://github.com/sol/hpack ----- hash: f761cc1b657f2445a77f2c2026a8f1b6bfae660f46caafca8ac668576cff708a+-- hash: 7836e6134ea2e8172dce2b5351da46ed4c9c9865c1f127c82a4b826f9bdee5e2  name:           grids-version:        0.5.0.0+version:        0.5.0.1 description:    Arbitrary sized type-safe grids with useful combinators category:       Data Structures homepage:       https://github.com/ChrisPenner/grids#readme

@@ -1,3 +1,8 @@+{-|+This module walks through implementing+<https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life Conway's Game of Live>+using @grids@. Read this module from top to bottom+-} {-# LANGUAGE DataKinds #-} {-# LANGUAGE OverloadedLists #-} {-# LANGUAGE ViewPatterns #-}@@ -9,27 +14,173 @@ import Data.List import Data.Functor.Compose -rule' :: Grid [3, 3] Bool -> Bool-rule' (partitionFocus -> (currentCellAlive, neighbours)) =+{-|+Conway's game of life is a form of <https://en.wikipedia.org/wiki/Cellular_automaton Cellular Automata>;+This means that it's a system of cells where a simulation is described in terms+of the __neighbourhood__ of a cell.+We'll implement the standard set of rules for Conway's Game of Life+using convolution with @grids@ (which you can read about on wikipedia)!++@grids@ provides the 'convolute' and 'autoConvolute' helpers to allow performing+neighbourhood-aware computations without too much trouble.++'autoConvolute' allows you to provide a window-size via a Type Application, a function+for adapting the coordinates of the neighbours, which is useful for providing+behaviour for cases where coordinates are out of bounds. Lastly we provide+a function which can reduce the provided neighbourhood of a cell back down to+a single cell which will be slotted into the final structure.++With these things in mind, we write our 'step' function which performs a single+simulation step on a 'Grid' using a window-reduction rule that we'll write next!++> step :: (IsGrid dims) => Grid dims Bool -> Grid dims Bool+> step = autoConvolute @[3, 3] wrapBounds rule++We use the 'wrapBounds' strategy for handling out-of-bounds indices which will+occur when trying to get the neighbourhood of cells along the edge of the grid.+'wrapBounds' means we'll grab the next cell from the opposite side of the grid,+wrapping around Pacman style.+-}+step :: (IsGrid dims) => Grid dims Bool -> Grid dims Bool+step = autoConvolute @[3, 3] wrapBounds rule++{-|+Next up we'll write the reduction rule itself. We've already decided to use a [3, 3]+neighbourhood in the previous step by using a Type Application, GHC could infer+it in thi case if we didn't provide it; but I find it helpful to be as clear+as possible.++So the goal is to go from a [3, 3] neighbourhood of a cell down to a single cell+again; the liveness of each cell is a 'Bool' which is 'True' if the cell is+alive, 'False' otherwise.++Take a look at how we do it:++> rule :: Grid [3, 3] Bool -> Bool+> rule window' =+>   (currentCellAlive && livingNeighbours == 2) || livingNeighbours == 3+>   where+>     (currentCellAlive, neighbours) = partitionFocus window'+>     livingNeighbours = length . filter id . toList . Compose $ neighbours++We'll start with the @where@ clauses.++Firstly we use the nifty 'partitionFocus' combinator which separates out the+center of a window from the surrounding neighbours as a tuple. Intuitively, We name+these parts @currentCellAlive@ and @neighbours@. Next we count how many neighbours+are actually alive by leaning on the 'Foldable' typeclass. 'partitionFocus' returns+the neighbours as a @Grid [3, 3] (Maybe Bool)@ in this case; so by wrapping it with+'Compose' we can fold over only the 'Just' values, e.g. the neighbours! We then+filter out the 'False' ones with @filter id@ and we know how many neighbours are+alive!++Back to the main definition, all that's left is to write the actual logic of the rule; there are many ways+to write in the rule; but I hope you trust I've picked a good one :D++That's it! By combining our rule with the powers of auto-convolution we've written+the core of Conway's game of life in just a dozen lines of code. Clever us!++Keep reading and we'll add some helpers so we can actually try running it.+-}+rule :: Grid [3, 3] Bool -> Bool+rule window' =   (currentCellAlive && livingNeighbours == 2) || livingNeighbours == 3   where+    (currentCellAlive, neighbours) = partitionFocus window'     livingNeighbours = length . filter id . toList . Compose $ neighbours -step :: (IsGrid dims) => Grid dims Bool -> Grid dims Bool-step = autoConvolute @[3, 3] wrapBounds rule'+{-|+If we're going to simulate a game we need to have a starting position! -glider :: [Coord '[10, 10]]-glider = Coord <$> [[0, 1], [1, 2], [2, 0], [2, 1], [2, 2]]+Let's start off with a glider hanging out in the top left corner. +Since we'll be using a 2 dimensional grid+we can draw out our grid as a list of lists (i.e. @[String]@) and use+'fromNestedLists'' to build it into a 'Grid' for us! Note that the trailing @'@+denotes the unsafe version of 'fromNestedLists' which will error if we give+it input that mismatches our expected dimensions, use the safe version unless+you're confident about your input sources!++> start :: Grid '[10, 10] Bool+> start = (== '#') <$> fromNestedLists'+>   [ ".#........"+>   , "..#......."+>   , "###......."+>   , ".........."+>   , ".........."+>   , ".........."+>   , ".........."+>   , ".........."+>   , ".........."+>   , ".........."+>   ]+-} start :: Grid '[10, 10] Bool-start = tabulate (`elem` glider)+start = (== '#') <$> fromNestedLists'+  [ ".#........"+  , "..#......."+  , "###......."+  , ".........."+  , ".........."+  , ".........."+  , ".........."+  , ".........."+  , ".........."+  , ".........."+  ] ++{-|+Now that we've got a good starting point we can run a few steps of our simulation+and see where we end up!++'step' is an Endomorphisn, i.e. a function from a type to the same type, so+we can use 'iterate' to generate an infinite list of steps where each subsequent+step is equal to applying the 'step' function on the previous iteration.++By using '!!' we can index into the infinite list and see what things look like+after a set number of iterations.++> simulate :: Int -> Grid '[10, 10] Bool+> simulate i = iterate step start !! i+-}+ simulate :: Int -> Grid '[10, 10] Bool-simulate = (iterate step start !!)+simulate i = iterate step start !! i -showBool :: Bool -> Char-showBool True = '#'-showBool False = '.' +{-|+The built-in show instance for 'Grid' isn't perfect, so let's write a nice+one for our simulation. We can extract our grid as a list of lists of @Bool@, i.e. @[[Bool]]@;+and collapse it into a string so we can print it to the console.++> showGrid :: (IsGrid '[x, y]) => Grid '[x, y] Bool -> String+> showGrid = intercalate "\n" . toNestedLists . fmap showBool+>   where+>     showBool :: Bool -> Char+>     showBool True = '#'+>     showBool False = '.'++Let's how far our glider can make it to after 10 iterations++> λ> putStrLn . showGrid $ simulate 10+> ..........+> ..........+> ..........+> ....#.....+> ..#.#.....+> ...##.....+> ..........+> ..........+> ..........+> ..........++That's it for this guide! Thanks!++-} showGrid :: (IsGrid '[x, y]) => Grid '[x, y] Bool -> String showGrid = intercalate "\n" . toNestedLists . fmap showBool+  where+    showBool :: Bool -> Char+    showBool True = '#'+    showBool False = '.'