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
valuesmap 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.