Note: You should use Data.Map.Strict instead of this module if:
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:
Operation comments contain the operation time complexity in the Big-O notation (http://en.wikipedia.org/wiki/Big_O_notation).
In some cases,
Data instances for abstract types are incorrect,
and fail to work correctly with Uniplate. This module defines three helper
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
Using the helper types, this module defines wrappers for types in
containers package, namely
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
type is defined as:
newtype Map k v = Map (
Trigger[v], Hide (Map.Map k v))) deriving (Data, Typeable)
Map type is defined as an
Invariant of three components - the keys, the values, and
Map. We use
Invariant to ensure that the keysvaluesmap always remain in sync.
Trigger on the keys and values to ensure that whenever the keys or values change we
Map, but if they don't, we reuse the previous
fromMap function is
implemented by pattern matching on 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)
create function creates a value from a
Map, getting the correct keys and values. The
function looks at the triggers on the keys/values. If the keys trigger has been tripped, then we
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.