conways-game-of-life/GOL/Space.hs

68 lines
2.2 KiB
Haskell
Raw Permalink Normal View History

2021-12-20 15:25:54 -05:00
{-# LANGUAGE AllowAmbiguousTypes #-}
2021-12-21 21:36:59 -05:00
{-# LANGUAGE DeriveFunctor #-}
2021-12-20 15:25:54 -05:00
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE TypeFamilies #-}
2021-12-20 14:24:16 -05:00
module GOL.Space where
2021-12-21 21:36:59 -05:00
import Data.Bifunctor
import Data.Distributive
2021-12-20 14:24:16 -05:00
import Data.Functor.Rep
2021-12-21 21:36:59 -05:00
import Data.Vector (Vector, (!))
import qualified Data.Vector as V
2021-12-20 14:24:16 -05:00
2021-12-20 16:20:51 -05:00
-- | A space in which a Conway's Game of Life simulation
-- takes place, with a notion of "neighbors to a cell" defined.
--
-- More specifically, a space is a representable functor @f@ such
2021-12-28 00:51:51 -05:00
-- that @'Rep' f@ is a simple undirected graph. 'neighbors' then
-- takes a node of that graph and returns all nodes that are adjacent.
2021-12-20 16:20:51 -05:00
--
-- Instances should satisfy:
--
-- * Symmetry: if @x '`elem`' 'neighbors' y@, then @y '`elem`' 'neighbors' x@.
--
-- * Irreflexivity: @x '`elem`' 'neighbors' x@ is always false.
2021-12-20 15:28:11 -05:00
class Representable f => Space f where
neighbors :: Rep f -> [Rep f]
2021-12-20 14:24:16 -05:00
2021-12-20 16:20:51 -05:00
-- | A space is _displayable_ if it is representable over a 2D
-- grid. The graphical system requires a displayable space.
2021-12-20 15:28:11 -05:00
class (Space f, Rep f ~ (Int, Int)) => DisplayableSpace f where
2021-12-20 16:20:51 -05:00
sizex :: Int
2021-12-21 21:36:59 -05:00
sizey :: Int
-- * Standard spaces
-- Unfortunately, due to the fact that Haskell doesn't have dependent types,
-- defining a GOL space to have an arbitrary size specified at runtime by
-- the user is completely impossible. There's simply no way to do it without
-- features that Haskell doesn't have.
-- So until we get generalized pi types in GHC, we'll have to make do with
-- hard-coded space sizes.
-- | A 100x100 2D grid space. This space is _toroidal_, which means that
-- cells on the opposite edges are considered neighbors of each other.
newtype ToroidalSpace a = TS (Vector (Vector a))
deriving (Show, Functor)
instance Distributive ToroidalSpace where
distribute xs = tabulate (\p -> fmap (`index` p) xs)
instance Representable ToroidalSpace where
type Rep ToroidalSpace = (Int, Int)
2021-12-28 18:17:19 -05:00
index (TS s) (i, j) = s ! i ! j
2021-12-21 21:36:59 -05:00
tabulate f = TS $ V.generate 100 (\x -> V.generate 100 $ \y -> f (x, y))
instance Space ToroidalSpace where
neighbors (i, j) =
bimap ((`mod` 100).(+i)) ((`mod` 100).(+j)) <$>
[
(-1,-1), (0,-1), (1,-1),
(-1, 0), (1, 0),
(-1, 1), (0, 1), (1, 1)
]
instance DisplayableSpace ToroidalSpace where
sizex = 100
sizey = 100