-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Tools for working with regular grids (graphs, lattices). -- -- Provides tools for working with regular arrangements of tiles, such as -- might be used in a board game or some other type of grid map. -- Currently supports triangular, square, and hexagonal tiles, with -- various 2D and toroidal layouts. The userguide is available at -- https://github.com/mhwombat/grid/wiki. -- -- NOTE: Version 4.0 uses associated (type) synonyms instead of -- multi-parameter type classes. -- -- NOTE: Version 3.0 changed the order of parameters for many functions. -- This makes it easier for the user to write mapping and folding -- operations. @package grid @version 4.1 -- | A module containing private Grid internals. Most developers -- should use Grid instead. This module is subject to change -- without notice. module Math.Geometry.GridInternal -- | A regular arrangement of tiles. Minimal complete definition: -- indices and distance. class Grid g where type family Index g minDistance g xs x = minimum . map (distance g x) $ xs neighbours g x = filter (\ a -> distance g x a ≡ 1) $ indices g numNeighbours g = length . neighbours g contains g x = x `elem` indices g viewpoint g p = map f (indices g) where f x = (x, distance g p x) tileCount = length . indices null g = tileCount g ≡ 0 nonNull = not . null edges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g isAdjacent g a b = a `elem` (neighbours g b) adjacentTilesToward g a b = filter f $ neighbours g a where f x = distance g x b ≡ distance g a b - 1 minimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ x -> minimalPaths g x b) ys ys = adjacentTilesToward g a b indices :: Grid g => g -> [Index g] distance :: Grid g => g -> Index g -> Index g -> Int minDistance :: Grid g => g -> [Index g] -> Index g -> Int neighbours :: Grid g => g -> Index g -> [Index g] numNeighbours :: Grid g => g -> Index g -> Int contains :: (Grid g, Eq (Index g)) => g -> Index g -> Bool viewpoint :: Grid g => g -> Index g -> [(Index g, Int)] tileCount :: Grid g => g -> Int null :: Grid g => g -> Bool nonNull :: Grid g => g -> Bool edges :: (Grid g, Eq (Index g)) => g -> [(Index g, Index g)] isAdjacent :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> Bool adjacentTilesToward :: Grid g => g -> Index g -> Index g -> [Index g] minimalPaths :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> [[Index g]] -- | A regular arrangement of tiles where the number of tiles is finite. -- Minimal complete definition: size. class Grid g => FiniteGrid g where type family Size s size :: FiniteGrid g => g -> Size g -- | A regular arrangement of tiles with an edge. Minimal complete -- definition: tileSideCount. class Grid g => BoundedGrid g where boundary g = map fst . filter f $ xds where xds = map (\ y -> (y, numNeighbours g y)) $ indices g f (_, n) = n < tileSideCount g isBoundary g x = x `elem` boundary g centre g = map fst . head . reverse . groupBy ((≡) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ y -> (y, minDistance g bs y)) $ indices g bs = boundary g isCentre g x = x `elem` centre g tileSideCount :: BoundedGrid g => g -> Int boundary :: BoundedGrid g => g -> [Index g] isBoundary :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool centre :: BoundedGrid g => g -> [Index g] isCentre :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool class Grid g => WrappedGrid g normalise :: WrappedGrid g => g -> Index g -> Index g data UnboundedTriGrid -- | A triangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TriTriGrid -- | triTriGrid s returns a triangular grid with sides of -- length s, using triangular tiles. If s is -- nonnegative, the resulting grid will have s^2 tiles. -- Otherwise, the resulting grid will be null and the list of indices -- will be null. triTriGrid :: Int -> TriTriGrid -- | A Parallelogrammatical grid with triangular tiles. The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaTriGrid -- | paraTriGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- triangular tiles. If r and c are both nonnegative, -- the resulting grid will have 2*r*c tiles. Otherwise, the -- resulting grid will be null and the list of indices will be null. paraTriGrid :: Int -> Int -> ParaTriGrid -- | A rectangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectTriGrid -- | rectTriGrid r c returns a grid in the shape of a -- rectangle (with jagged edges) that has r rows and c -- columns, using triangular tiles. If r and c are both -- nonnegative, the resulting grid will have 2*r*c tiles. -- Otherwise, the resulting grid will be null and the list of indices -- will be null. rectTriGrid :: Int -> Int -> RectTriGrid -- | A toroidal grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorTriGrid -- | torTriGrid r c returns a toroidal grid with r -- rows and c columns, using triangular tiles. If r is -- odd, the result is undefined because the grid edges would overlap. If -- r and c are both nonnegative, the resulting grid -- will have 2*r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. torTriGrid :: Int -> Int -> TorTriGrid data UnboundedSquareGrid -- | A rectangular grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectSquareGrid -- | rectSquareGrid r c produces a rectangular grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. rectSquareGrid :: Int -> Int -> RectSquareGrid -- | A toroidal grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorSquareGrid -- | torSquareGrid r c returns a toroidal grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. torSquareGrid :: Int -> Int -> TorSquareGrid data UnboundedHexGrid -- | A hexagonal grid with hexagonal tiles The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data HexHexGrid -- | hexHexGrid s returns a grid of hexagonal shape, with -- sides of length s, using hexagonal tiles. If s is -- nonnegative, the resulting grid will have 3*s*(s-1) + 1 -- tiles. Otherwise, the resulting grid will be null and the list of -- indices will be null. hexHexGrid :: Int -> HexHexGrid -- | A parallelogramatical grid with hexagonal tiles The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaHexGrid -- | paraHexGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- hexagonal tiles. If r and c are both nonnegative, -- the resulting grid will have r*c tiles. Otherwise, the -- resulting grid will be null and the list of indices will be null. paraHexGrid :: Int -> Int -> ParaHexGrid instance Show UnboundedTriGrid instance Eq TriTriGrid instance Eq ParaTriGrid instance Eq RectTriGrid instance Eq TorTriGrid instance Show UnboundedSquareGrid instance Eq RectSquareGrid instance Eq TorSquareGrid instance Show UnboundedHexGrid instance Eq HexHexGrid instance Eq ParaHexGrid instance BoundedGrid ParaHexGrid instance FiniteGrid ParaHexGrid instance Grid ParaHexGrid instance Show ParaHexGrid instance BoundedGrid HexHexGrid instance FiniteGrid HexHexGrid instance Grid HexHexGrid instance Show HexHexGrid instance Grid UnboundedHexGrid instance WrappedGrid TorSquareGrid instance FiniteGrid TorSquareGrid instance Grid TorSquareGrid instance Show TorSquareGrid instance BoundedGrid RectSquareGrid instance FiniteGrid RectSquareGrid instance Grid RectSquareGrid instance Show RectSquareGrid instance Grid UnboundedSquareGrid instance WrappedGrid TorTriGrid instance FiniteGrid TorTriGrid instance Grid TorTriGrid instance Show TorTriGrid instance BoundedGrid RectTriGrid instance FiniteGrid RectTriGrid instance Grid RectTriGrid instance Show RectTriGrid instance BoundedGrid ParaTriGrid instance FiniteGrid ParaTriGrid instance Grid ParaTriGrid instance Show ParaTriGrid instance BoundedGrid TriTriGrid instance FiniteGrid TriTriGrid instance Grid TriTriGrid instance Show TriTriGrid instance Grid UnboundedTriGrid -- | A regular arrangement of tiles. Grids have a variety of uses, -- including games and self-organising maps. The userguide is available -- at https://github.com/mhwombat/grid/wiki. -- -- NOTE: Version 4.0 uses associated (type) synonyms instead of -- multi-parameter type classes. module Math.Geometry.Grid -- | A regular arrangement of tiles. Minimal complete definition: -- indices and distance. class Grid g where type family Index g minDistance g xs x = minimum . map (distance g x) $ xs neighbours g x = filter (\ a -> distance g x a ≡ 1) $ indices g numNeighbours g = length . neighbours g contains g x = x `elem` indices g viewpoint g p = map f (indices g) where f x = (x, distance g p x) tileCount = length . indices null g = tileCount g ≡ 0 nonNull = not . null edges g = nubBy sameEdge $ concatMap (`adjacentEdges` g) $ indices g isAdjacent g a b = a `elem` (neighbours g b) adjacentTilesToward g a b = filter f $ neighbours g a where f x = distance g x b ≡ distance g a b - 1 minimalPaths g a b | a ≡ b = [[a]] | distance g a b ≡ 1 = [[a, b]] | otherwise = map (a :) xs where xs = concatMap (\ x -> minimalPaths g x b) ys ys = adjacentTilesToward g a b indices :: Grid g => g -> [Index g] distance :: Grid g => g -> Index g -> Index g -> Int minDistance :: Grid g => g -> [Index g] -> Index g -> Int neighbours :: Grid g => g -> Index g -> [Index g] numNeighbours :: Grid g => g -> Index g -> Int contains :: (Grid g, Eq (Index g)) => g -> Index g -> Bool viewpoint :: Grid g => g -> Index g -> [(Index g, Int)] tileCount :: Grid g => g -> Int null :: Grid g => g -> Bool nonNull :: Grid g => g -> Bool edges :: (Grid g, Eq (Index g)) => g -> [(Index g, Index g)] isAdjacent :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> Bool adjacentTilesToward :: Grid g => g -> Index g -> Index g -> [Index g] minimalPaths :: (Grid g, Eq (Index g)) => g -> Index g -> Index g -> [[Index g]] -- | A regular arrangement of tiles where the number of tiles is finite. -- Minimal complete definition: size. class Grid g => FiniteGrid g where type family Size s size :: FiniteGrid g => g -> Size g -- | A regular arrangement of tiles with an edge. Minimal complete -- definition: tileSideCount. class Grid g => BoundedGrid g where boundary g = map fst . filter f $ xds where xds = map (\ y -> (y, numNeighbours g y)) $ indices g f (_, n) = n < tileSideCount g isBoundary g x = x `elem` boundary g centre g = map fst . head . reverse . groupBy ((≡) `on` snd) . sortBy (comparing snd) $ xds where xds = map (\ y -> (y, minDistance g bs y)) $ indices g bs = boundary g isCentre g x = x `elem` centre g tileSideCount :: BoundedGrid g => g -> Int boundary :: BoundedGrid g => g -> [Index g] isBoundary :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool centre :: BoundedGrid g => g -> [Index g] isCentre :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> Bool data UnboundedTriGrid -- | A triangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TriTriGrid -- | triTriGrid s returns a triangular grid with sides of -- length s, using triangular tiles. If s is -- nonnegative, the resulting grid will have s^2 tiles. -- Otherwise, the resulting grid will be null and the list of indices -- will be null. triTriGrid :: Int -> TriTriGrid -- | A Parallelogrammatical grid with triangular tiles. The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaTriGrid -- | paraTriGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- triangular tiles. If r and c are both nonnegative, -- the resulting grid will have 2*r*c tiles. Otherwise, the -- resulting grid will be null and the list of indices will be null. paraTriGrid :: Int -> Int -> ParaTriGrid -- | A rectangular grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectTriGrid -- | rectTriGrid r c returns a grid in the shape of a -- rectangle (with jagged edges) that has r rows and c -- columns, using triangular tiles. If r and c are both -- nonnegative, the resulting grid will have 2*r*c tiles. -- Otherwise, the resulting grid will be null and the list of indices -- will be null. rectTriGrid :: Int -> Int -> RectTriGrid -- | A toroidal grid with triangular tiles. The grid and its indexing -- scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorTriGrid -- | torTriGrid r c returns a toroidal grid with r -- rows and c columns, using triangular tiles. If r is -- odd, the result is undefined because the grid edges would overlap. If -- r and c are both nonnegative, the resulting grid -- will have 2*r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. torTriGrid :: Int -> Int -> TorTriGrid data UnboundedSquareGrid -- | A rectangular grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data RectSquareGrid -- | rectSquareGrid r c produces a rectangular grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. rectSquareGrid :: Int -> Int -> RectSquareGrid -- | A toroidal grid with square tiles. The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data TorSquareGrid -- | torSquareGrid r c returns a toroidal grid with -- r rows and c columns, using square tiles. If -- r and c are both nonnegative, the resulting grid -- will have r*c tiles. Otherwise, the resulting grid will be -- null and the list of indices will be null. torSquareGrid :: Int -> Int -> TorSquareGrid data UnboundedHexGrid -- | A hexagonal grid with hexagonal tiles The grid and its indexing scheme -- are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data HexHexGrid -- | hexHexGrid s returns a grid of hexagonal shape, with -- sides of length s, using hexagonal tiles. If s is -- nonnegative, the resulting grid will have 3*s*(s-1) + 1 -- tiles. Otherwise, the resulting grid will be null and the list of -- indices will be null. hexHexGrid :: Int -> HexHexGrid -- | A parallelogramatical grid with hexagonal tiles The grid and its -- indexing scheme are illustrated in the user guide, available at -- https://github.com/mhwombat/grid/wiki. data ParaHexGrid -- | paraHexGrid r c returns a grid in the shape of a -- parallelogram with r rows and c columns, using -- hexagonal tiles. If r and c are both nonnegative, -- the resulting grid will have r*c tiles. Otherwise, the -- resulting grid will be null and the list of indices will be null. paraHexGrid :: Int -> Int -> ParaHexGrid -- | Ordered maps from tiles on a grid to values. This module is a wrapper -- around Grid and Map, in order to -- combine the functionality of grids and maps into a single type. module Math.Geometry.GridMap class (Grid (BaseGrid gm v), Foldable gm) => GridMap (gm :: * -> *) v where type family BaseGrid gm v ! gm k = toMap gm ! k toList = toList . toMap lookup k = lookup k . toMap adjust f = adjustWithKey (\ _ v -> f v) findWithDefault v k = findWithDefault v k . toMap elems = elems . toMap map f = mapWithKey (\ _ v -> f v) (!) :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => gm v -> k -> v toMap :: (GridMap gm v, k ~ (Index (BaseGrid gm v))) => gm v -> Map k v toGrid :: GridMap gm v => gm v -> BaseGrid gm v toList :: (GridMap gm v, k ~ (Index (BaseGrid gm v))) => gm v -> [(k, v)] lookup :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => k -> gm v -> Maybe v adjust :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => (v -> v) -> k -> gm v -> gm v adjustWithKey :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => (k -> v -> v) -> k -> gm v -> gm v findWithDefault :: (GridMap gm v, k ~ (Index (BaseGrid gm v)), Ord k) => v -> k -> gm v -> v elems :: GridMap gm v => gm v -> [v] map :: (GridMap gm v, GridMap gm b) => (v -> b) -> gm v -> gm b mapWithKey :: (GridMap gm v, k ~ Index (BaseGrid gm v), GridMap gm v2) => (k -> v -> v2) -> gm v -> gm v2 -- | O(n). Fold the values in the map using the given -- right-associative binary operator, such that foldr f z == -- foldr f z . elems. -- -- For example, -- -- 
--   elems map = foldr (:) [] map
--
-- -- 
--   let f a len = len + (length a)
--   foldr f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldr :: (a -> b -> b) -> b -> Map k a -> b -- | O(n). A strict version of foldr. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldr' :: (a -> b -> b) -> b -> Map k a -> b -- | O(n). Fold the values in the map using the given -- left-associative binary operator, such that foldl f z == -- foldl f z . elems. -- -- For example, -- -- 
--   elems = reverse . foldl (flip (:)) []
--
-- -- 
--   let f len a = len + (length a)
--   foldl f 0 (fromList [(5,"a"), (3,"bbb")]) == 4
--
foldl :: (a -> b -> a) -> a -> Map k b -> a -- | O(n). A strict version of foldl. Each application of the -- operator is evaluated before using the result in the next application. -- This function is strict in the starting value. foldl' :: (a -> b -> a) -> a -> Map k b -> a -- | Ordered maps from tiles on a grid to values. This module is a wrapper -- around Grid and Map, in order to -- combine the functionality of grids and maps into a single type. module Math.Geometry.GridMap.Lazy -- | A map from tile positions in a grid to values. data LGridMap g v -- | Construct a grid map which is strict in the keys (tile positions), but -- lazy in the values. lazyGridMap :: (Ord (Index g), Grid g) => g -> [v] -> LGridMap g v instance (Show g, Show v) => Show (LGridMap g v) instance (Eq g, Eq (Index g), Eq v) => Eq (LGridMap g v) instance Grid g => GridMap (LGridMap g) v instance FiniteGrid g => FiniteGrid (LGridMap g v) instance Grid g => Grid (LGridMap g v) instance Foldable (LGridMap g) instance (Grid g, Ord (Index g)) => Functor (LGridMap g)