Portability | portable |
---|---|

Stability | experimental |

Maintainer | amy@nualeargais.ie |

Safe Haskell | Safe-Inferred |

- data GridMap g k v
- lazyGridMap :: (Ord k, Grid g s k) => g -> [v] -> GridMap g k v
- indices :: Grid g s x => g -> [x]
- distance :: Grid g s x => g -> x -> x -> Int
- size :: Grid g s x => g -> s
- neighbours :: Grid g s x => g -> x -> [x]
- contains :: Grid g s x => g -> x -> Bool
- viewpoint :: Grid g s x => g -> x -> [(x, Int)]
- tileCount :: Grid g s x => g -> Int
- empty :: Grid g s x => g -> Bool
- nonEmpty :: Grid g s x => g -> Bool
- (!) :: Ord k => GridMap g k v -> k -> v
- lookup :: Ord k => k -> GridMap g k v -> Maybe v
- findWithDefault :: Ord k => v -> k -> GridMap g k v -> v
- adjust :: Ord k => (v -> v) -> k -> GridMap g k v -> GridMap g k v
- adjustWithKey :: Ord k => (k -> v -> v) -> k -> GridMap g k v -> GridMap g k v
- map :: (a -> b) -> GridMap g k a -> GridMap g k b
- mapWithKey :: (k -> a -> b) -> GridMap g k a -> GridMap g k b
- mapAccum :: (a -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c)
- mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c)
- fold :: (a -> b -> a) -> a -> GridMap g k b -> a
- foldWithKey :: (a -> k -> b -> a) -> a -> GridMap g k b -> a
- fold' :: (a -> b -> a) -> a -> GridMap g k b -> a
- foldWithKey' :: (a -> k -> b -> a) -> a -> GridMap g k b -> a
- elems :: GridMap g k a -> [a]
- keysSet :: GridMap g k a -> Set k
- toList :: GridMap g k a -> [(k, 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 ----------------+------------------------------- assocs |`toList`

empty |`lazyGridMap`

g [] foldl |`fold`

foldl' |`fold'`

foldlWithKey |`foldWithKey`

foldlWithKey' |`foldWithKey'`

foldr |`fold`

foldr' |`fold'`

foldrWithKey |`foldWithKey`

foldrWithKey' |`foldWithKey'`

fromList |`lazyGridMap`

fromListWithKey |`lazyGridMap`

fromListWith |`lazyGridMap`

fromSet |`lazyGridMap`

keys |`indices`

member |`inGrid`

notMember | not`inGrid`

null |`empty`

singleton |`lazyGridMap`

g [v] size |`size`

,`tileCount`

The functions (\), `alter`

, `delete`

, `deleteFindMax`

, `deleteFindMin`

,
`deleteMax`

, `deleteMin`

, `difference`

, `differenceWith`

, `differenceWithKey`

,
`filter`

, `filterWithKey`

, `insert`

, `insertLookupWithKey`

, `insertWith`

,
`insertWithKey`

, `intersection`

, `intersectionWith`

, `intersectionWithKey`

,
`isProperSubmapOf`

, `isProperSubmapOfBy`

, `isSubmapOf`

, `isSubmapOf`

,
`isSubmapOfBy`

, `mapEither`

, `mapEitherWithKey`

, `mapKeys`

, `mapKeysWith`

,
`mapMaybe`

, `mapMaybeWithKey`

, `mergeWithKey`

, `partition`

,
`partitionWithKey`

, `split`

, `splitLookup`

, `traverseWithKey`

, `union`

,
`unions`

, `unionsWith`

, `unionWith`

, `unionWithKey`

, `update`

,
`updateLookupWithKey`

and `updateWithKey`

are not implemented because the
resulting map might have different dimensions than the original, or because
they combine maps of different dimensions.
As a result, these functions may not be as useful for grid maps.
If you need one of these functions, you can extract the map using `toMap`

and apply the function from `Data.Map`

to the result.

The functions `deleteAt`

, `elemAt`

, `findIndex`

, `findMax`

, `findMin`

,
`fromAscList`

, `fromAscListWith`

, `fromAscListWithKey`

, `fromDistinctAscList`

,
`lookupGE`

, `lookupGT`

, `lookupIndex`

, `lookupLE`

, `lookupLT`

,
`mapAccumRWithKey`

, `mapKeysMonotonic`

, `maxView`

, `maxViewWithKey`

,
`minView`

, `minViewWithKey`

, `toAscList`

, `toDescList`

, `updateAt`

,
`updateMax`

, `updateMaxWithKey`

, `updateMin`

and `updateMinWithKey`

are not
implemented because they rely on a meaningful ordering of keys.
While tile positions can be ordered (e.g., `(1,2) < (2,1)`

), the ordering
may not be relevant to grid maps.
(Comparisons such as *east of* or *south of* may be more meaningful.)
If you need one of these functions, you can extract the map using `toMap`

and apply the function from `Data.Map`

to the result.

The debugging functions `showTree`

, `showTreeWith`

and `valid`

are not
implemented.
If you need one of these functions, you can extract the map using `toMap`

and apply the function from `Data.Map`

to the result.

# Map type

A Map from tile positions in a grid to values.

# Construction

lazyGridMap :: (Ord k, Grid g s k) => g -> [v] -> GridMap g k vSource

Construct a grid map which is strict in the keys (tile positions), but lazy in the values.

# Grid functions

distance :: Grid g s x => g -> x -> x -> IntSource

returns the minimum number of moves required
to get from the tile at index `distance`

g a b`a`

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.

neighbours :: Grid g s x => g -> x -> [x]Source

returns the indices of the tiles in the grid
`neighbours`

g x`g`

which are adjacent to the tile with index `x`

.

contains :: Grid g s x => g -> x -> BoolSource

`g `'contains'` x`

returns `True`

if the index `x`

is contained
within the grid `g`

, otherwise it returns false.

viewpoint :: Grid g s x => g -> x -> [(x, Int)]Source

returns a list of pairs associating the index
of each tile in `viewpoint`

g x`g`

with its distance to the tile with index `x`

.
If `x`

is not contained within `g`

, the result is undefined.

empty :: Grid g s x => g -> BoolSource

Returns `True`

if the number of tiles in a grid is zero, `False`

otherwise.

nonEmpty :: Grid g s x => g -> BoolSource

Returns `False`

if the number of tiles in a grid is zero, `True`

otherwise.

# Map functions

## Operators

(!) :: Ord k => GridMap g k v -> k -> vSource

*O(min(n,W))*. Find the value at a tile position in the grid.
Calls `error`

when the element can not be found.

## Query

lookup :: Ord k => k -> GridMap g k v -> Maybe vSource

*O(min(n,W))*. Lookup the value at a tile position in the grid map.

findWithDefault :: Ord k => v -> k -> GridMap g k v -> vSource

*O(min(n,W))*. 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.

## Update

adjust :: Ord k => (v -> v) -> k -> GridMap g k v -> GridMap g k vSource

*O(min(n,W))*. 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 :: Ord k => (k -> v -> v) -> k -> GridMap g k v -> GridMap g k vSource

*O(min(n,W))*. Adjust a value at a specific key. When the tile
is not within the bounds of the grid map, the original grid map is
returned.

## Map

map :: (a -> b) -> GridMap g k a -> GridMap g k bSource

*O(n)*. Map a function over all values in the grid map.

mapWithKey :: (k -> a -> b) -> GridMap g k a -> GridMap g k bSource

*O(n)*. Map a function over all values in the grid map.

mapAccum :: (a -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c)Source

*O(n)*. The function

threads an accumulating
argument through the grid map.
WARNING: The order in which the elements are processed is not guaranteed.
`mapAccum`

mapAccumWithKey :: (a -> k -> b -> (a, c)) -> a -> GridMap g k b -> (a, GridMap g k c)Source

*O(n)*. The function

threads an accumulating
argument through the grid map.
WARNING: The order in which the elements are processed is not guaranteed.
`mapAccumWithKey`

## Folds

fold :: (a -> b -> a) -> a -> GridMap g k b -> aSource

*O(n)*. Fold the values in the grid map using the given left-associative
binary operator.
WARNING: The order in which the elements are processed is not guaranteed.

foldWithKey :: (a -> k -> b -> a) -> a -> GridMap g k b -> aSource

*O(n)*. Fold the keys and values in the grid map using the given
left-associative binary operator.
WARNING: The order in which the elements are processed is not guaranteed.

foldWithKey' :: (a -> k -> b -> a) -> a -> GridMap g k b -> aSource

*O(n)*. A strict version of `foldWithKey`

.

## Conversion

elems :: GridMap g k a -> [a]Source

*O(n)*.
Return all elements of the grid map. The order is not guaranteed.

keysSet :: GridMap g k a -> Set kSource

*O(n*min(n,W))*. The set of all tile positions in the grid map.