Module
Instances

uniplate - Data.Generics.Uniplate.Data.Instances

In some cases, `Data`

instances for abstract types are incorrect,
and fail to work correctly with Uniplate. This module defines three helper
types (`Hide`

, `Trigger`

and `Invariant`

) to assist when writing instances
for abstract types. The `Hide`

type is useful when you want to mark some part
of your data type as being ignored by Data.Generics.Uniplate.Data
(and any other `Data`

based generics libraries, such as `syb`

).

Using the helper types, this module defines wrappers for types in
the `containers`

package, namely `Map`

, `Set`

, `IntMap`

and `IntSet`

.
The standard `containers`

`Data`

instances all treat the types as abstract,
but the wrapper types allow you to traverse within the data types, ensuring
the necessary invariants are maintained. In particular, if you do not modify
the keys reconstruct will be *O(n)* instead of *O(n log n)*.

As an example of how to implement your own abstract type wrappers, the `Map`

data
type is defined as:

newtype Map k v = Map (`Invariant`

(`Trigger`

[k],`Trigger`

[v], Hide (Map.Map k v))) deriving (Data, Typeable)

The `Map`

type is defined as an `Invariant`

of three components - the keys, the values, and
the underlying `Map`

. We use `Invariant`

to ensure that the keys*values*map always remain in sync.
We use `Trigger`

on the keys and values to ensure that whenever the keys or values change we
rebuild the `Map`

, but if they don't, we reuse the previous `Map`

. The `fromMap`

function is
implemented by pattern matching on the `Map`

type:

`fromMap`

(`Map`

(`Invariant`

_ (_,_,`Hide`

x))) = x

The `toMap`

function is slightly harder, as we need to come up with an invariant restoring function:

toMap :: Ord k => Map.Map k v -> Map k v toMap x = Map $ Invariant inv $ create x where create x = (Trigger False ks, Trigger False vs, Hide x) where (ks,vs) = unzip $ Map.toAscList x inv (ks,vs,x) | trigger ks = create $ Map.fromList $ zip (fromTrigger ks) (fromTrigger vs) | trigger vs = create $ Map.fromDistinctAscList $ zip (fromTrigger ks) (fromTrigger vs) | otherwise = (ks,vs,x)

The `create`

function creates a value from a `Map`

, getting the correct keys and values. The `inv`

function looks at the triggers on the keys/values. If the keys trigger has been tripped, then we
reconstruct the `Map`

using `fromList`

. If the values trigger has been tripped, but they keys trigger
has not, we can use `fromDistinctAscList`

, reducing the complexity of constructing the `Map`

. If nothing
has changed we can reuse the previous value.

The end result is that all Uniplate (or `syb`

) traversals over `Map`

result in a valid value, which has
had all appropriate transformations applied.

check-pvp
Package

Check whether module and package imports conform to the PVP

Module
Lens

One of most commonly-asked questions about this package is whether
it provides lenses for working with `Map`

. It does, but their uses
are perhaps obscured by their genericity. This module exists to provide
documentation for them.

`Map`

is an instance of `At`

, so we have a lenses
on values at keys:

`>>>`

Just "world"`Map.fromList [(1, "world")] ^.at 1`

`>>>`

fromList [(1,"world")]`at 1 .~ Just "world" $ Map.empty`

`>>>`

fromList [(0,"hello")]`at 0 ?~ "hello" $ Map.empty`

We can traverse, fold over, and map over key-value pairs in a
`Map`

, thanks to its `TraversableWithIndex`

,
`FoldableWithIndex`

, and
`FunctorWithIndex`

instances.

`>>>`

fromList [(1,1)]`imap const $ Map.fromList [(1, "Venus")]`

`>>>`

Sum {getSum = 5}`ifoldMap (\i _ -> Sum i) $ Map.fromList [(2, "Earth"), (3, "Mars")]`

`>>>`

(4,"Jupiter")`itraverse_ (curry print) $ Map.fromList [(4, "Jupiter")]`

`>>>`

[(5,"Saturn")]`itoList $ Map.fromList [(5, "Saturn")]`

A related class, `Ixed`

, allows us to use
`ix`

to traverse a value at a particular key.

`>>>`

fromList [(2,"New Earth")]`ix 2 %~ ("New " ++) $ Map.fromList [(2, "Earth")]`

`>>>`

Nothing`preview (ix 8) $ Map.empty`

Additionally, `Map`

has `TraverseMin`

and
`TraverseMax`

instances, which let us traverse over
the value at the least and greatest keys, respectively.

`>>>`

Just "Saturn"`preview traverseMin $ Map.fromList [(5, "Saturn"), (6, "Uranus")]`

`>>>`

Just "Uranus"`preview traverseMax $ Map.fromList [(5, "Saturn"), (6, "Uranus")]`

Data
MapVector

vector-space-map - Data.Map.Vector

Note: `<*>`

in the `Applicative`

instance operates under *intersection*. i.e.:

`>>>`

MapVector (Map.fromList [])`(MapVector $ Map.fromList [("x", id)]) <*> (MapVector $ Map.fromList [("y", 3)])`

`*`

in the `Num`

instance performs elementwise multiplication. It is defined in terms of
`<*>`

and therefore also operates under intersection:

`>>>`

MapVector (Map.fromList [("x", 10), ("y", 21)])`(MapVector $ Map.fromList [("x", 2), ("y", 3)]) * (MapVector $ Map.fromList [("x", 5),("y", 7)])`

`>>>`

MapVector (Map.fromList [("y", 21)])`(MapVector $ Map.fromList [("x", 2), ("y", 3)]) * (MapVector $ Map.fromList [("y", 7)])`

`*^`

in the `VectorSpace`

instance multiplies by the scalar of v. Nesting MapVectors preserves
the scalar type, e.g. `Scalar (MapVector k (MapVector k' v))`

= `Scalar v`

.

`>>>`

ConstantMap (MapVector (fromList [("x",6),("y",10)]))`2 *^ (ConstantMap $ MapVector $ Map.fromList [("x", 3 :: Int), ("y", 5)])`

Finally, `<.>`

in `InnerSpace`

is the dot-product operator. Again, it operates under intersection.

`>>>`

31`(MapVector $ Map.fromList [("x", 2 :: Int), ("y", 3)]) <.> (MapVector $ Map.fromList [("x", 5),("y", 7)])`

`>>>`

25`(pure . MapVector $ Map.fromList [("x", 2 :: Int), ("y", 3)]) <.> (MapVector $ Map.fromList [("a", pure (5::Int))])`

Module
Map

*Note:* You should use Data.Map.Strict instead of this module if:

- You will eventually need all the values stored.
- The stored values don't represent large virtual data structures to be lazily computed.

An efficient implementation of ordered maps from keys to values (dictionaries).

These modules are intended to be imported qualified, to avoid name clashes with Prelude functions, e.g.

import qualified Data.Map as Map

The implementation of `Map`

is based on *size balanced* binary trees (or
trees of *bounded balance*) as described by:

- Stephen Adams, "
*Efficient sets: a balancing act*", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB/. - J. Nievergelt and E.M. Reingold,
"
*Binary search trees of bounded balance*", SIAM journal of computing 2(1), March 1973.

Note that the implementation is *left-biased* -- the elements of a
first argument are always preferred to the second, for example in
`union`

or `insert`

.

Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).

map
:: (a -> b) -> Map k a -> Map k b

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

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

map
:: (a -> b) -> Map k a -> Map k b

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

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

map
:: (a -> b) -> v a -> v b

fixed-vector - Data.Vector.Fixed

Map over vector

map
:: (Int -> Int) -> IntDisjointSet -> IntDisjointSet

disjoint-set - Data.IntDisjointSet

Map each member to another Int. The map function must be a bijection, i.e. 1-to-1 mapping.

map
:: (a -> b) -> MultiMap k a -> MultiMap k b

Map a function over all values in the map.

map
:: (VCardValue -> VCardValue) -> [VCard] -> [VCard]

Map by property value only.

map
:: (a -> b) -> IntMap a -> IntMap b

containers - Data.IntMap.Strict

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

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

map
:: (a -> b) -> SetMap k a -> SetMap k b

Map a function over all values in the map.

map
:: (Bool -> Bool) -> α -> α

bitstream - Data.Bitstream.Generic Data.Bitstream.Lazy Data.Bitstream

*O(n)* Map a function over a `Bitstream`

.

map
:: (a -> b) -> Map k a -> Map k b

Map a function over all values in the map.

map
:: (v -> v) -> HamtMap k v -> HamtMap k v

Map a function over all values in the map.

map
:: (a -> b) -> IntMap a -> IntMap b

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

map (++ "x") (fromList [(5,"a"), (3,"b")]) == fromList [(3, "bx"), (5, "ax")]

map
:: (a -> b) -> Vector a -> Vector b

*O(n)* Map a function over a vector

map
:: (a -> b) -> NonEmpty a -> NonEmpty b

semigroups - Data.List.NonEmpty

Map a function over a `NonEmpty`

stream.

map
:: (a -> b) -> BDictMap a -> BDictMap b

bencoding - Data.BEncode.BDict

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