Portability | portable |
---|---|
Stability | experimental |
Maintainer | amy@nualeargais.ie |
Safe Haskell | Safe-Inferred |
- class (Grid (BaseGrid gm v), Foldable gm) => GridMap gm v where
- type BaseGrid gm v
- (!) :: (k ~ Index (BaseGrid gm v), Ord k) => gm v -> k -> v
- toMap :: k ~ Index (BaseGrid gm v) => gm v -> Map k v
- toGrid :: gm v -> BaseGrid gm v
- toList :: k ~ Index (BaseGrid gm v) => gm v -> [(k, v)]
- lookup :: (k ~ Index (BaseGrid gm v), Ord k) => k -> gm v -> Maybe v
- adjust :: (k ~ Index (BaseGrid gm v), Ord k) => (v -> v) -> k -> gm v -> gm v
- adjustWithKey :: (k ~ Index (BaseGrid gm v), Ord k) => (k -> v -> v) -> k -> gm v -> gm v
- findWithDefault :: (k ~ Index (BaseGrid gm v), Ord k) => v -> k -> gm v -> v
- elems :: gm v -> [v]
- map :: GridMap gm b => (v -> b) -> gm v -> gm b
- mapWithKey :: (k ~ Index (BaseGrid gm v), GridMap gm v2) => (k -> v -> v2) -> gm v -> gm v2
- class Grid g where
- type Index g
- indices :: g -> [Index g]
- distance :: g -> Index g -> Index g -> Int
- minDistance :: g -> [Index g] -> Index g -> Int
- neighbours :: g -> Index g -> [Index g]
- numNeighbours :: g -> Index g -> Int
- contains :: Eq (Index g) => g -> Index g -> Bool
- viewpoint :: g -> Index g -> [(Index g, Int)]
- tileCount :: g -> Int
- null :: g -> Bool
- nonNull :: g -> Bool
- edges :: Eq (Index g) => g -> [(Index g, Index g)]
- isAdjacent :: Eq (Index g) => g -> Index g -> Index g -> Bool
- adjacentTilesToward :: g -> Index g -> Index g -> [Index g]
- minimalPaths :: Eq (Index g) => g -> Index g -> Index g -> [[Index g]]
- size :: FiniteGrid g => g -> Size g
- 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
- foldr :: (a -> b -> b) -> b -> Map k a -> b
- foldr' :: (a -> b -> b) -> b -> Map k a -> b
- foldl :: (a -> b -> a) -> a -> Map k b -> a
- foldl' :: (a -> b -> a) -> a -> Map k b -> a
Differences between GridMap
and Map
.
Some functions in Data.Map
have been replaced in GridMap
.
These changes are listed in the table below.
Map function | corresponding GridMap function --------------------+---------------------------------------------- ! | ! \ | See note 1 empty |lazyGridMap
g [] findWithDefault |findWithDefault
insert | See notes 1, 2 lookup |lookup
lookupLE | See notes 1, 3 lookupLT | See notes 1, 3 lookupGE | See notes 1, 3 lookupGT | See notes 1, 3 member |inGrid
notMember | notinGrid
null |null
singleton |lazyGridMap
g [v] size |size
,tileCount
* insert | See notes 1, 2 insertWith | See notes 1, 2 insertWithKey | See notes 1, 2 insertLookupWithKey | See notes 1, 2 delete | See notes 1, 2 adjust |adjust
adjustWithKey |adjustWithKey
update | See notes 1, 2 updateWithKey | See notes 1, 2 updateLookupWithKey | See notes 1, 2 alter | See notes 1, 2 union | See notes 1, 2 unionWith | See notes 1, 2 unionWithKey | See notes 1, 2 unions | See notes 1, 2 unionsWith | See notes 1, 2 difference | See notes 1, 2 differenceWith | See notes 1, 2 differenceWithKey | See notes 1, 2 intersection | See notes 1, 2 intersectionWith | See notes 1, 2 intersectionWithKey | See notes 1, 2 mergeWithKey | See notes 1, 2 M.map | fmap, or see note 1 mapWithKey | See note 1 traverseWithKey | See notes 1, 2 mapAccum | See note 1 mapAccumWithKey | See note 1 mapAccumRWithKey | See note 1 mapKeys | See note 1 mapKeysWith | See note 1 mapKeysMonotonic | See note 1 foldr | See note 1 foldl | See note 1 foldrWithKey | See note 1 foldlWithKey | See note 1 foldr' | See note 1 foldl' | See note 1 foldrWithKey' | See note 1 foldlWithKey' | See note 1 elems |elems
keys |indices
assocs | See note 1 keysSet | See note 1 fromSet |lazyGridMap
(constructor) toList | See note 1 fromList |lazyGridMap
(constructor) fromListWithKey |lazyGridMap
(constructor) fromListWith |lazyGridMap
(constructor) toAscList | See notes 1, 3 toDescList | See notes 1, 3 fromAscList | See notes 1, 3 fromAscListWith | See notes 1, 3 fromAscListWithKey | See notes 1, 3 fromDistinctAscList | See notes 1, 3 filter | See notes 1, 2 filterWithKey | See notes 1, 2 partition | See notes 1, 2 partitionWithKey | See notes 1, 2 mapMaybe | See notes 1, 2 mapMaybeWithKey | See notes 1, 2 mapEither | See notes 1, 2 mapEitherWithKey | See notes 1, 2 split | See notes 1, 2 splitLookup | See notes 1, 2 isSubmapOf | See note 1 isSubmapOfBy | See note 1 isProperSubmapOf | See note 1 isProperSubmapOfBy | See note 1 lookupIndex | See note 1 findIndex | See note 1 elemAt | See note 1 updateAt | See note 1 deleteAt | See notes 1, 2 findMin | See notes 1, 3 findMax | See notes 1, 3 deleteMin | See notes 1, 2, 3 deleteMax | See notes 1, 2, 3 deleteFindMin | See notes 1, 2, 3 deleteFindMax | See notes 1, 2, 3 updateMin | See notes 1, 2, 3 updateMax | See notes 1, 2, 3 updateMinWithKey | See notes 1, 2, 3 updateMaxWithKey | See notes 1, 2, 3 minView | See notes 1, 3 maxView | See notes 1, 3 minViewWithKey | See notes 1, 2, 3 maxViewWithKey | See notes 1, 2, 3 showTree | See note 1 showTreeWith | See note 1 valid | See note 1
Notes:
1. You can extract the map using
and apply the function from
toMap
Data.Map
to the result.
- Not implemented because the resulting map might have different
dimensions than the original input
GridMap
(s). However, you can extract the map using
and apply the function fromtoMap
Data.Map
to the result. - Not implemented because, although tile positions can be ordered
(e.g.,
(1,2) < (2,1)
), the ordering may not be meaningful for grid maps. Comparisons such as east of or south of may be more useful. However, you can extract the map using
and apply the function fromtoMap
Data.Map
to the result.
Map classes and types
class (Grid (BaseGrid gm v), Foldable gm) => GridMap gm v whereSource
(!) :: (k ~ Index (BaseGrid gm v), Ord k) => gm v -> k -> vSource
Find the value at a tile position in the grid.
toMap :: k ~ Index (BaseGrid gm v) => gm v -> Map k vSource
Returns a map of grid indices to values.
toGrid :: gm v -> BaseGrid gm vSource
Returns the grid on which this map is based.
toList :: k ~ Index (BaseGrid gm v) => gm v -> [(k, v)]Source
Convert the map to a list of key/value pairs.
lookup :: (k ~ Index (BaseGrid gm v), Ord k) => k -> gm v -> Maybe vSource
Lookup the value at a tile position in the grid map.
adjust :: (k ~ Index (BaseGrid gm v), Ord k) => (v -> v) -> k -> gm v -> gm vSource
Adjust a value at a specific tile position. When the tile is not within the bounds of the grid map, the original grid map is returned.
adjustWithKey :: (k ~ Index (BaseGrid gm v), Ord k) => (k -> v -> v) -> k -> gm v -> gm vSource
Adjust a value at a specific tile position. When the tile is not within the bounds of the grid map, the original grid map is returned.
findWithDefault :: (k ~ Index (BaseGrid gm v), Ord k) => v -> k -> gm v -> vSource
The expression (
returns the value
at tile position findWithDefault
def k map)k
or returns def
when the tile is not within
the bounds of the grid map.
Returns all values in the map
map :: GridMap gm b => (v -> b) -> gm v -> gm bSource
Map a function over all values in the map.
mapWithKey :: (k ~ Index (BaseGrid gm v), GridMap gm v2) => (k -> v -> v2) -> gm v -> gm v2Source
Map a function over all values in the map.
A regular arrangement of tiles.
Minimal complete definition: indices
and distance
.
indices :: g -> [Index g]Source
Returns the indices of all tiles in a grid.
distance :: g -> Index g -> Index g -> IntSource
returns the minimum number of moves required
to get from the tile at index distance
g a ba
to the tile at index b
in
grid g
, moving between adjacent tiles at each step. (Two tiles
are adjacent if they share an edge.) If a
or b
are not
contained within g
, the result is undefined.
minDistance :: g -> [Index g] -> Index g -> IntSource
returns the minimum number of moves
required to get from any of the tiles at indices minDistance
g bs abs
to the tile
at index a
in grid g
, moving between adjacent tiles at each
step. (Two tiles are adjacent if they share an edge.) If a
or
any of bs
are not contained within g
, the result is
undefined.
neighbours :: g -> Index g -> [Index g]Source
returns the indices of the tiles in the grid
neighbours
g xg
which are adjacent to the tile with index x
.
numNeighbours :: g -> Index g -> IntSource
returns the number of tiles in the grid
numNeighbours
g xg
which are adjacent to the tile with index x
.
contains :: Eq (Index g) => g -> Index g -> BoolSource
g `'contains'` x
returns True
if the index x
is contained
within the grid g
, otherwise it returns false.
viewpoint :: g -> Index g -> [(Index g, Int)]Source
returns a list of pairs associating the index
of each tile in viewpoint
g xg
with its distance to the tile with index x
.
If x
is not contained within g
, the result is undefined.
Returns the number of tiles in a grid. Compare with
.
size
Returns True
if the number of tiles in a grid is zero, False
otherwise.
Returns False
if the number of tiles in a grid is zero, True
otherwise.
edges :: Eq (Index g) => g -> [(Index g, Index g)]Source
A list of all edges in a grid, where the edges are represented by a pair of indices of adjacent tiles.
isAdjacent :: Eq (Index g) => g -> Index g -> Index g -> BoolSource
returns isAdjacent
g a bTrue
if the tile at index a
is
adjacent to the tile at index b
in g
. (Two tiles are adjacent
if they share an edge.) If a
or b
are not contained within
g
, the result is undefined.
adjacentTilesToward :: g -> Index g -> Index g -> [Index g]Source
returns the indices of all tiles
which are neighbours of the tile at index adjacentTilesToward
g a ba
, and which are
closer to the tile at b
than a
is. In other words, it returns
the possible next steps on a minimal path from a
to b
. If a
or b
are not contained within g
, or if there is no path from
a
to b
(e.g., a disconnected grid), the result is undefined.
minimalPaths :: Eq (Index g) => g -> Index g -> Index g -> [[Index g]]Source
returns a list of all minimal paths from
the tile at index minimalPaths
g a ba
to the tile at index b
in grid g
. A
path is a sequence of tiles where each tile in the sequence is
adjacent to the previous one. (Two tiles are adjacent if they
share an edge.) If a
or b
are not contained within g
, the
result is undefined.
Tip: The default implementation of this function calls
. If you want to use a custom algorithm,
consider modifying adjacentTilesToward
instead of
adjacentTilesToward
.
minimalPaths
Deconstruction
Grid functions
size :: FiniteGrid g => g -> Size gSource
boundary :: BoundedGrid g => g -> [Index g]Source
Returns a the indices of all the tiles at the boundary of a grid.
isBoundary :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> BoolSource
' returns isBoundary
g xTrue
if the tile with index x
is
on a boundary of g
, False
otherwise. (Corner tiles are also
boundary tiles.)
centre :: BoundedGrid g => g -> [Index g]Source
Returns the index of the tile(s) that require the maximum number of moves to reach the nearest boundary tile. A grid may have more than one central tile (e.g., a rectangular grid with an even number of rows and columns will have four central tiles).
isCentre :: (BoundedGrid g, Eq (Index g)) => g -> Index g -> BoolSource
' returns isCentre
g xTrue
if the tile with index x
is
a centre tile of g
, False
otherwise.
Map functions
Operators
Query
Update
Traversal
Folds
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.
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.