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 keysvaluesmap 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 whether module and package imports conform to the PVP

lens - Data.Map.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:

>>> Map.fromList [(1, "world")] ^.at 1
Just "world"
>>> at 1 .~ Just "world" $ Map.empty
fromList [(1,"world")]
>>> at 0 ?~ "hello" $ Map.empty
fromList [(0,"hello")]

We can traverse, fold over, and map over key-value pairs in a Map, thanks to its TraversableWithIndex, FoldableWithIndex, and FunctorWithIndex instances.

>>> imap const $ Map.fromList [(1, "Venus")]
fromList [(1,1)]
>>> ifoldMap (\i _ -> Sum i) $ Map.fromList [(2, "Earth"), (3, "Mars")]
Sum {getSum = 5}
>>> itraverse_ (curry print) $ Map.fromList [(4, "Jupiter")]
(4,"Jupiter")
>>> itoList $ Map.fromList [(5, "Saturn")]
[(5,"Saturn")]

A related class, Ixed, allows us to use ix to traverse a value at a particular key.

>>> ix 2 %~ ("New " ++) $ Map.fromList [(2, "Earth")]
fromList [(2,"New Earth")]
>>> preview (ix 8) $ Map.empty
Nothing

Additionally, Map has TraverseMin and TraverseMax instances, which let us traverse over the value at the least and greatest keys, respectively.

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

vector-space-map - Data.Map.Vector  

Note: <*> in the Applicative instance operates under intersection. i.e.:

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

* in the Num instance performs elementwise multiplication. It is defined in terms of <*> and therefore also operates under intersection:

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

*^ 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.

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

Finally, <.> in InnerSpace is the dot-product operator. Again, it operates under intersection.

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

Addition, using either + or ^+^, operates under union.

containers - Data.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

containers - Data.Map.Lazy  

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

containers - Data.Map.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 :: (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

multimap - Data.MultiMap  

Map a function over all values in the map.

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

vcard - Text.VCard.Query  

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

multimap - Data.SetMap  

Map a function over all values in the map.

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

hashmap - Data.HashMap  

Map a function over all values in the map.

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

hamtmap - Data.HamtMap  

Map a function over all values in the map.

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

containers - Data.IntMap.Lazy  

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

vector - Data.Vector.Storable  

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.