-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A set of classes and instances for working with key/value mappings. -- -- Basically a broad extension to the IArray interface for all -- sorts of key/value maps. -- -- Arrays, maps etc can all use these classes so datatypes can be swapped -- in and out of algorithms. -- -- The classes have plenty of functions, but also many default -- implementations, so making instances for your datatypes should be -- relatively easy. -- -- Of course, if you give specialised defintions you might get better -- performance for some operations. -- -- Currently only deals with pure structures but mutable structures are -- next on the todo list. @package map-classes @version 0.1.0.0 -- | If you just want to perform operations on maps, not write your own -- instances, Control.Class.Map is probably what you should be -- importing. -- -- This package provides a number of type-classes that encapulate the -- idea of a key/value mapping. This includes your standard maps, but -- also arrays and potentially hashtables. This library only currently -- provide instances for types in package that are distributed with GHC. -- -- Part of the motivation of this library is also consistency. -- -- Pop quiz: Consider the insert, but don't check the -- documentation. If the key already exists in the map, which of the -- following occurs? -- --
    --
  1. The map is unchanged.
    2. --
  2. The value at that key is updated.
    3. --
  3. error is called.
    4. --
  4. The result is undefined.
    5. --
-- -- Personally, I had to check the documentation. The answer is actually -- option "2". -- -- Imagine the potential minefield when changing collection types. -- -- The classes in this library give explicit names for each of these -- behaviours, and if the implementers of those instances follow those -- specifications, users should be able to switch between different -- container types without changing their code nor their code's -- behaviour. -- -- The naming convention and argument order is somewhat arbitary. -- -- I've tried to follow existing convention but the existing convention -- is a bit mixed up. -- -- For example insert for maps is actually called upsert in -- this library because that's what it actually does. -- -- In anycase, I'll attempt to define the broad naming convention here, -- but there are further details in each class. -- -- There's a number of prefixes to function which affect expected -- behaviour. -- --
    --
  1. The unprefixed functions should call error if something is -- unexpected, e.g. a key already exists on insert or a key is not -- in collection on delete. They must not just return the -- structure unchanged, that is the role of maybe prefixed -- functions.
    2. --
  2. The "unsafe" prefixed functions may optionally just behave in an -- undefined fashion in the above case where one would instead -- error. For example, unsafe functions may do array -- lookups without bounds checking, potentially resulting in demons if -- they access memory they shouldn't.
    3. --
  3. The "maybe" prefixed functions shall not call error if the -- operation can not be completed but instead return the structure -- unchanged.
    4. --
  4. The "safe" prefixed functions actually have a Maybe return -- type which indicate whether the key is not found/already exists on -- insert.
    5. --
-- -- Functions suffixed with Lookup actually have a different return -- type and generally allow one to access the contents of the structure -- before the change, the exact form depending on the function in -- particular. The reason for the Lookup suffix is that to -- implement these naively one can do a lookup before performing the -- operation. However, for example with deleteLookup on a map, it -- would be more efficient to just lookup the element to delete, grab it -- and delete it at the same time, so there is a point in overriding the -- default implementation. -- -- Finally, you may notice some of the class functions that ordinarily -- accept a Functor, are renamed ending with a ..F_, and -- now have the Functor wrapped in a Coyoneda. This is -- because having Functors in class function defintions does not -- work with generalised newtype deriving. -- -- The versions of the functions without the following underscores, i.e. -- ..F are what users should be using. When defining your own -- instances for these functions, it's probably best just apply -- 'toCoyonedaTransform'/'toCoyonedaTransformF' to their ordinary -- definitions. The non underscore style defintions run -- 'fromCoyonedaTransform'/'fromCoyonedaTransformF' on the class -- functions. Ideally rewrite rules included in these modules should -- reduce this pair of functions to id resulting in no runtime -- difference. -- -- Regarding trailing F on the latter -- 'toCoyonedaTransform'/'toCoyonedaTransformF' function, use that when -- defining such Coyondea class functions which have return -- types wrapped in Maybe, namely the ones prefixed with -- safe.... -- -- To Do: Monadic versions of these functions, to be used on mutable -- structures for example. -- -- Also To Do: Range lookups (and perhaps even range deletes?). In -- theory, for say maps, range lookups are not only possible but also -- faster than accessing the keys individually. But they've impossible -- for say hashmaps. -- -- Pull requests welcome on github. module Control.Class.Impl.Map -- | LookupMap is a class that simply represents data types -- indexable by a key that you can read from. Whilst obviously not -- enforced by the class, it's intended that this only be implemented for -- types with "fast" lookups, say O(log n) at most. -- -- Hence, LookupMap is not implemented for list for example. -- -- Not that Set is an instance of this type, where the keys are -- just the set values and the unit type '()' is the "value" type. -- -- You could in theory implement LookupMap (and indeed associated -- classes like UpdateMap and AlterMap) for structures with -- multiple keys, by making the key type a sum type or a list or -- something. class LookupMap t -- | lookup k x returns Just v if k is a key, -- Nothing otherwise lookup :: LookupMap t => Key t -> t -> Maybe (Value t) -- | Like lookup but throws an error for values that don't exist index :: LookupMap t => Key t -> t -> Value t -- | Like index but may be undefined for keys that don't exist unsafeIndex :: LookupMap t => Key t -> t -> Value t member :: LookupMap t => Key t -> t -> Bool notMember :: LookupMap t => Key t -> t -> Bool -- | Data types you can produce a one element container of. -- -- The reason why this is a separate class instead of just the default -- instance is that there are contrainers where one can trivially make a -- singleton of but they're not Monoids or AlterMaps, i.e. -- you can't append or add elements to them at arbitary keys. -- -- For example, arrays certainly don't have the concept of "insert at -- key", only update, nor is it obvious how to append them, particularly -- if their ranges overlap. -- -- But given a key, one should be able to produce a singleton array. -- -- Hence this class. class LookupMap t => SingletonMap t singleton :: SingletonMap t => Key t -> Value t -> t -- | InsertMap represents types where new key-values pairs can be -- inserted. class LookupMap t => InsertMap t -- | Attempts to insert a value, calls error if the key already -- exists. insert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists the behaviour is -- undefined. unsafeInsert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists return the structure -- unchanged. maybeInsert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists return -- Nothing. safeInsert :: InsertMap t => Key t -> Value t -> t -> Maybe t -- | Like insert, but if the key already exists return -- Nothing. safeInsert :: (InsertMap t, UpsertMap t) => Key t -> Value t -> t -> Maybe t -- | UpdateMap represents types where existing values can be -- updated. -- -- The ability for keys to be inserted or deleted is optional. -- -- A good example of a type which conforms to this is Seq, which -- has Int keys of which their values can be updated in "O(log n)" -- time. -- -- However Seq is not an instance of AlterMap as although -- one can insert/delete from Seq it alters all the other indexes -- which would be very unexpected. class LookupMap t => UpdateMap t -- | Updates the value of a key, calls error if the key does not -- exist. update :: UpdateMap t => Key t -> Value t -> t -> t updateLookup :: UpdateMap t => Key t -> Value t -> t -> (Value t, t) -- | Like update, but if the key does not exist the result is -- undefined. unsafeUpdate :: UpdateMap t => Key t -> Value t -> t -> t unsafeUpdateLookup :: UpdateMap t => Key t -> Value t -> t -> (Value t, t) maybeUpdate :: UpdateMap t => Key t -> Value t -> t -> t safeUpdate :: UpdateMap t => Key t -> Value t -> t -> Maybe t safeUpdateLookup :: UpdateMap t => Key t -> Value t -> t -> Maybe (Value t, t) -- | adjust f k x applies f to the value at key -- k and puts that modified value in it's place. -- -- If the key does not exist it should throw an error. adjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t adjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> (r, t) adjustF_ :: (UpdateMap t, Functor f) => (Value t -> Coyoneda f (Value t)) -> Key t -> t -> Coyoneda f t unsafeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t unsafeAdjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> (r, t) unsafeAdjustF_ :: (UpdateMap t, Functor f) => (Value t -> Coyoneda f (Value t)) -> Key t -> t -> Coyoneda f t maybeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t safeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> Maybe t safeAdjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> Maybe (r, t) safeAdjustF_ :: (UpdateMap t, Functor f) => (Value t -> Coyoneda f (Value t)) -> Key t -> t -> Maybe (Coyoneda f t) safeAdjustF_ :: (UpdateMap t, UpsertMap t, Functor f) => (Value t -> Coyoneda f (Value t)) -> Key t -> t -> Maybe (Coyoneda f t) adjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> f t unsafeAdjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> f t safeAdjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> Maybe (f t) -- | DeleteMap represents types where keys can be deleted. class LookupMap t => DeleteMap t -- | Attempt to delete a key and call error if it's not found. delete :: DeleteMap t => Key t -> t -> t -- | Like delete, but also return the value at the key before -- deletion. deleteLookup :: DeleteMap t => Key t -> t -> (Value t, t) -- | Like delete but if the key isn't found the result is undefined unsafeDelete :: DeleteMap t => Key t -> t -> t -- | Like deleteLookup but if the key isn't found the result is -- undefined unsafeDeleteLookup :: DeleteMap t => Key t -> t -> (Value t, t) -- | Like delete, but return the structure unmodified if the key -- does not exist. maybeDelete :: DeleteMap t => Key t -> t -> t -- | Like delete, but return Nothing the key does not exist. safeDelete :: DeleteMap t => Key t -> t -> Maybe t -- | Like safeDelete, but also return the value of the key before -- the delete. safeDeleteLookup :: DeleteMap t => Key t -> t -> Maybe (Value t, t) -- | Attempt to optDelete a key based on it's value and call error -- if it's not found. optDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDelete, but also return the value at the key before -- deletion. optDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> (r, t) optDeleteF_ :: (DeleteMap t, Functor f) => (Value t -> Coyoneda f Bool) -> Key t -> t -> Coyoneda f t -- | Like optDelete but if the key isn't found the result is -- undefined unsafeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDeleteLookup but if the key isn't found the result is -- undefined unsafeOptDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> (r, t) unsafeOptDeleteF_ :: (DeleteMap t, Functor f) => (Value t -> Coyoneda f Bool) -> Key t -> t -> Coyoneda f t -- | Like optDelete, but return the structure unmodified if the key -- does not exist. maybeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDelete, but return Nothing the key does not -- exist. safeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> Maybe t -- | Like safeOptDelete, but also return the value of the key before -- the optDelete. safeOptDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> Maybe (r, t) safeOptDeleteF_ :: (DeleteMap t, Functor f) => (Value t -> Coyoneda f Bool) -> Key t -> t -> Maybe (Coyoneda f t) safeOptDeleteF_ :: (DeleteMap t, UpleteMap t, Functor f) => (Value t -> Coyoneda f Bool) -> Key t -> t -> Maybe (Coyoneda f t) optDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> f t unsafeOptDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> f t safeOptDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> Maybe (f t) -- | Functions for doing inserts that don't fail on the keys being found -- but instead override existing values. class (InsertMap t, UpdateMap t) => UpsertMap t upsert :: UpsertMap t => Key t -> Value t -> t -> t upsertLookup :: UpsertMap t => Key t -> Value t -> t -> (Maybe (Value t), t) adsert :: UpsertMap t => (Maybe (Value t) -> Value t) -> Key t -> t -> t adsertLookup :: UpsertMap t => (Maybe (Value t) -> (r, Value t)) -> Key t -> t -> (r, t) adsertF_ :: (UpsertMap t, Functor f) => (Maybe (Value t) -> Coyoneda f (Value t)) -> Key t -> t -> Coyoneda f t adsertF_ :: (UpsertMap t, AlterMap t, Functor f) => (Maybe (Value t) -> Coyoneda f (Value t)) -> Key t -> t -> Coyoneda f t adsertF :: (UpsertMap t, Functor f) => (Maybe (Value t) -> f (Value t)) -> Key t -> t -> f t class (DeleteMap t, UpdateMap t) => UpleteMap t adlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t adleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) adleteF_ :: (UpleteMap t, Functor f) => (Value t -> Coyoneda f (Maybe (Value t))) -> Key t -> t -> Coyoneda f t unsafeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t unsafeAdleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) unsafeAdleteF_ :: (UpleteMap t, Functor f) => (Value t -> Coyoneda f (Maybe (Value t))) -> Key t -> t -> Coyoneda f t maybeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t safeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> Maybe t safeAdleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> Maybe (r, t) safeAdleteF_ :: (UpleteMap t, Functor f) => (Value t -> Coyoneda f (Maybe (Value t))) -> Key t -> t -> Maybe (Coyoneda f t) safeAdleteF_ :: (UpleteMap t, AlterMap t, Functor f) => (Value t -> Coyoneda f (Maybe (Value t))) -> Key t -> t -> Maybe (Coyoneda f t) adleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> f t unsafeAdleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> f t safeAdleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> Maybe (f t) -- | AlterMap is a class that represents key-value mappings where -- one can do inserts, deletes, updates, pretty much everything you -- expect from a simple key/value store. class (UpsertMap t, UpleteMap t) => AlterMap t -- | alter f k x attempts to gets the value of the key k. -- -- If key k exists, as say it is v, it passes Just -- v to f. -- -- If key k does not exist, it passes Nothing to -- f. -- -- If the result of f is Just something, then -- alter either inserts or updates the key k, inserting -- if key k previously didn't exist and updating if it did. -- -- If the result of f is Nothing, and the key -- k did exist, we deleted it. -- -- Otherwise, if the result of f is Nothing, nd the key -- k did not exist, then do nothing and simply return the -- structure unmodified. alter :: AlterMap t => (Maybe (Value t) -> Maybe (Value t)) -> Key t -> t -> t -- | Like alter, but returns the value both before and after the -- alteration. alterLookup :: AlterMap t => (Maybe (Value t) -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) alterF_ :: (AlterMap t, Functor f) => (Maybe (Value t) -> Coyoneda f (Maybe (Value t))) -> Key t -> t -> Coyoneda f t alterF :: (AlterMap t, Functor f) => (Maybe (Value t) -> f (Maybe (Value t))) -> Key t -> t -> f t -- | For certain types like maps in the standard containers library that -- ships with GHC, the strict version of the data type: Map, and -- the lazy version of the data type: Map, are actually the exact -- same type. In this case, they're just reexports of the same type. -- -- That's fine when one has two separate modules with strict and lazy -- versions one can explicitly use, but the choice can't be automatic -- based on the type. -- -- As a result, there's no way one can tell whether to use strict or lazy -- functions on the data. Wrapping these types in either Strict or -- Lazy specifies how these types are intend to be worked on. -- -- By default however, if one doesn't wrap, the Strict version is -- used. newtype Strict t Strict :: t -> Strict t [getStrict] :: Strict t -> t -- | See Strict documentation for a discussion of the Lazy -- wrapper. newtype Lazy t Lazy :: t -> Lazy t [getLazy] :: Lazy t -> t (!) :: LookupMap t => t -> Key t -> Value t -- | Hack to allow generalised newtype deriving from -- https://stackoverflow.com/questions/48848571/generalised-newtype-deriving-on-class-functions-with-functors/48849568#48849568 fromCoyonedaTransform :: Functor f1 => ((a1 -> Coyoneda f2 a2) -> t1 -> t2 -> Coyoneda f1 a3) -> (a1 -> f2 a2) -> t1 -> t2 -> f1 a3 fromCoyonedaTransformF :: (Functor f1, Functor f3) => ((a1 -> Coyoneda f2 a2) -> t1 -> t2 -> f3 (Coyoneda f1 a3)) -> (a1 -> f2 a2) -> t1 -> t2 -> f3 (f1 a3) toCoyonedaTransform :: Functor f => (forall f'. Functor f' => (a1 -> f' a2) -> t1 -> t2 -> f' a3) -> ((a1 -> Coyoneda f a2) -> t1 -> t2 -> Coyoneda f a3) toCoyonedaTransformF :: Functor f => (forall f'. Functor f' => (a1 -> f' a2) -> t1 -> t2 -> f3 (f' a3)) -> ((a1 -> Coyoneda f a2) -> t1 -> t2 -> f3 (Coyoneda f a3)) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.LookupMap t) => Control.Class.Impl.Map.LookupMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.InsertMap t) => Control.Class.Impl.Map.InsertMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.UpdateMap t) => Control.Class.Impl.Map.UpdateMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.DeleteMap t) => Control.Class.Impl.Map.DeleteMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.UpsertMap t) => Control.Class.Impl.Map.UpsertMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.UpleteMap t) => Control.Class.Impl.Map.UpleteMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsStrictMap t, Control.Class.Impl.Map.AlterMap t) => Control.Class.Impl.Map.AlterMap (Control.Class.Impl.Map.Strict t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.LookupMap t) => Control.Class.Impl.Map.LookupMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.InsertMap t) => Control.Class.Impl.Map.InsertMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.UpdateMap t) => Control.Class.Impl.Map.UpdateMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.DeleteMap t) => Control.Class.Impl.Map.DeleteMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.UpsertMap t) => Control.Class.Impl.Map.UpsertMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.UpleteMap t) => Control.Class.Impl.Map.UpleteMap (Control.Class.Impl.Map.Lazy t) instance (Control.Class.Impl.Map.IsLazyMap t, Control.Class.Impl.Map.AlterMap t) => Control.Class.Impl.Map.AlterMap (Control.Class.Impl.Map.Lazy t) instance Control.Class.Impl.Map.IsLazyMap t => Control.Class.Impl.Map.IsLazyMap (Control.Class.Impl.Map.Lazy t) instance Control.Class.Impl.Map.IsLazyMap (Data.Set.Internal.Set a) instance Control.Class.Impl.Map.IsLazyMap (GHC.Arr.Array i e) instance Control.Class.Impl.Map.IsStrictMap t => Control.Class.Impl.Map.IsStrictMap (Control.Class.Impl.Map.Strict t) instance Control.Class.Impl.Map.IsStrictMap (Data.Map.Internal.Map k v) instance Control.Class.Impl.Map.IsStrictMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.IsStrictMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord k => Control.Class.Impl.Map.LookupMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.SingletonMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.InsertMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpdateMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.DeleteMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpsertMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpleteMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance GHC.Classes.Ord k => Control.Class.Impl.Map.AlterMap (Control.Class.Impl.Map.Lazy (Data.Map.Internal.Map k v)) instance Control.Class.Impl.Map.LookupMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.SingletonMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.InsertMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.UpdateMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.DeleteMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.UpsertMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.UpleteMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.AlterMap (Control.Class.Impl.Map.Lazy (Data.IntMap.Internal.IntMap v)) instance Control.Class.Impl.Map.AppendMap (Data.Sequence.Internal.Seq a) instance GHC.Classes.Ord k => Control.Class.Impl.Map.InsertMap (Data.Map.Internal.Map k v) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpdateMap (Data.Map.Internal.Map k v) instance GHC.Classes.Ord k => Control.Class.Impl.Map.DeleteMap (Data.Map.Internal.Map k v) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpsertMap (Data.Map.Internal.Map k v) instance GHC.Classes.Ord k => Control.Class.Impl.Map.UpleteMap (Data.Map.Internal.Map k v) instance GHC.Classes.Ord k => Control.Class.Impl.Map.AlterMap (Data.Map.Internal.Map k v) instance Control.Class.Impl.Map.InsertMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.UpdateMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.DeleteMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.UpsertMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.UpleteMap (Data.IntMap.Internal.IntMap v) instance Control.Class.Impl.Map.AlterMap (Data.IntMap.Internal.IntMap v) instance GHC.Classes.Ord a => Control.Class.Impl.Map.InsertMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord a => Control.Class.Impl.Map.DeleteMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord a => Control.Class.Impl.Map.UpdateMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord a => Control.Class.Impl.Map.UpsertMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord a => Control.Class.Impl.Map.UpleteMap (Data.Set.Internal.Set a) instance GHC.Classes.Ord a => Control.Class.Impl.Map.AlterMap (Data.Set.Internal.Set a) instance Control.Class.Impl.Map.InsertMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.DeleteMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.UpdateMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.UpsertMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.UpleteMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.AlterMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.UpdateMap (Data.Sequence.Internal.Seq a) instance GHC.Classes.Ord k => Control.Class.Impl.Map.SingletonMap (Data.Map.Internal.Map k v) instance Control.Class.Impl.Map.SingletonMap (Data.IntMap.Internal.IntMap v) instance GHC.Classes.Ord a => Control.Class.Impl.Map.SingletonMap (Data.Set.Internal.Set a) instance Control.Class.Impl.Map.SingletonMap Data.IntSet.Internal.IntSet instance GHC.Arr.Ix i => Control.Class.Impl.Map.SingletonMap (GHC.Arr.Array i e) instance GHC.Classes.Ord k => Control.Class.Impl.Map.LookupMap (Data.Map.Internal.Map k v) instance Control.Class.Impl.Map.LookupMap (Data.IntMap.Internal.IntMap v) instance GHC.Classes.Ord a => Control.Class.Impl.Map.LookupMap (Data.Set.Internal.Set a) instance Control.Class.Impl.Map.LookupMap Data.IntSet.Internal.IntSet instance Control.Class.Impl.Map.LookupMap (Data.Sequence.Internal.Seq a) instance GHC.Arr.Ix i => Control.Class.Impl.Map.LookupMap (GHC.Arr.Array i e) instance Control.Class.Impl.Map.LookupMap Data.ByteString.Internal.ByteString instance Control.Class.Impl.Map.LookupMap Data.ByteString.Lazy.Internal.ByteString instance Control.Class.Impl.Map.LookupMap Data.ByteString.Short.Internal.ShortByteString -- | Exports the functions non instances writers should need. -- -- If you want to write your own instances (or indeed just want a general -- readme for the class) see the module Control.Class.Impl.Map module Control.Class.Map -- | LookupMap is a class that simply represents data types -- indexable by a key that you can read from. Whilst obviously not -- enforced by the class, it's intended that this only be implemented for -- types with "fast" lookups, say O(log n) at most. -- -- Hence, LookupMap is not implemented for list for example. -- -- Not that Set is an instance of this type, where the keys are -- just the set values and the unit type '()' is the "value" type. -- -- You could in theory implement LookupMap (and indeed associated -- classes like UpdateMap and AlterMap) for structures with -- multiple keys, by making the key type a sum type or a list or -- something. class LookupMap t -- | lookup k x returns Just v if k is a key, -- Nothing otherwise lookup :: LookupMap t => Key t -> t -> Maybe (Value t) -- | Like lookup but throws an error for values that don't exist index :: LookupMap t => Key t -> t -> Value t -- | Like index but may be undefined for keys that don't exist unsafeIndex :: LookupMap t => Key t -> t -> Value t member :: LookupMap t => Key t -> t -> Bool notMember :: LookupMap t => Key t -> t -> Bool -- | Data types you can produce a one element container of. -- -- The reason why this is a separate class instead of just the default -- instance is that there are contrainers where one can trivially make a -- singleton of but they're not Monoids or AlterMaps, i.e. -- you can't append or add elements to them at arbitary keys. -- -- For example, arrays certainly don't have the concept of "insert at -- key", only update, nor is it obvious how to append them, particularly -- if their ranges overlap. -- -- But given a key, one should be able to produce a singleton array. -- -- Hence this class. class LookupMap t => SingletonMap t singleton :: SingletonMap t => Key t -> Value t -> t -- | InsertMap represents types where new key-values pairs can be -- inserted. class LookupMap t => InsertMap t -- | Attempts to insert a value, calls error if the key already -- exists. insert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists the behaviour is -- undefined. unsafeInsert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists return the structure -- unchanged. maybeInsert :: InsertMap t => Key t -> Value t -> t -> t -- | Like insert, but if the key already exists return -- Nothing. safeInsert :: InsertMap t => Key t -> Value t -> t -> Maybe t -- | Like insert, but if the key already exists return -- Nothing. safeInsert :: (InsertMap t, UpsertMap t) => Key t -> Value t -> t -> Maybe t -- | UpdateMap represents types where existing values can be -- updated. -- -- The ability for keys to be inserted or deleted is optional. -- -- A good example of a type which conforms to this is Seq, which -- has Int keys of which their values can be updated in "O(log n)" -- time. -- -- However Seq is not an instance of AlterMap as although -- one can insert/delete from Seq it alters all the other indexes -- which would be very unexpected. class LookupMap t => UpdateMap t -- | Updates the value of a key, calls error if the key does not -- exist. update :: UpdateMap t => Key t -> Value t -> t -> t updateLookup :: UpdateMap t => Key t -> Value t -> t -> (Value t, t) -- | Like update, but if the key does not exist the result is -- undefined. unsafeUpdate :: UpdateMap t => Key t -> Value t -> t -> t unsafeUpdateLookup :: UpdateMap t => Key t -> Value t -> t -> (Value t, t) maybeUpdate :: UpdateMap t => Key t -> Value t -> t -> t safeUpdate :: UpdateMap t => Key t -> Value t -> t -> Maybe t safeUpdateLookup :: UpdateMap t => Key t -> Value t -> t -> Maybe (Value t, t) -- | adjust f k x applies f to the value at key -- k and puts that modified value in it's place. -- -- If the key does not exist it should throw an error. adjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t adjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> (r, t) unsafeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t unsafeAdjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> (r, t) maybeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> t safeAdjust :: UpdateMap t => (Value t -> Value t) -> Key t -> t -> Maybe t safeAdjustLookup :: UpdateMap t => (Value t -> (r, Value t)) -> Key t -> t -> Maybe (r, t) adjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> f t unsafeAdjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> f t safeAdjustF :: (UpdateMap t, Functor f) => (Value t -> f (Value t)) -> Key t -> t -> Maybe (f t) -- | DeleteMap represents types where keys can be deleted. class LookupMap t => DeleteMap t -- | Attempt to delete a key and call error if it's not found. delete :: DeleteMap t => Key t -> t -> t -- | Like delete, but also return the value at the key before -- deletion. deleteLookup :: DeleteMap t => Key t -> t -> (Value t, t) -- | Like delete but if the key isn't found the result is undefined unsafeDelete :: DeleteMap t => Key t -> t -> t -- | Like deleteLookup but if the key isn't found the result is -- undefined unsafeDeleteLookup :: DeleteMap t => Key t -> t -> (Value t, t) -- | Like delete, but return the structure unmodified if the key -- does not exist. maybeDelete :: DeleteMap t => Key t -> t -> t -- | Like delete, but return Nothing the key does not exist. safeDelete :: DeleteMap t => Key t -> t -> Maybe t -- | Like safeDelete, but also return the value of the key before -- the delete. safeDeleteLookup :: DeleteMap t => Key t -> t -> Maybe (Value t, t) -- | Attempt to optDelete a key based on it's value and call error -- if it's not found. optDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDelete, but also return the value at the key before -- deletion. optDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> (r, t) -- | Like optDelete but if the key isn't found the result is -- undefined unsafeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDeleteLookup but if the key isn't found the result is -- undefined unsafeOptDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> (r, t) -- | Like optDelete, but return the structure unmodified if the key -- does not exist. maybeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> t -- | Like optDelete, but return Nothing the key does not -- exist. safeOptDelete :: DeleteMap t => (Value t -> Bool) -> Key t -> t -> Maybe t -- | Like safeOptDelete, but also return the value of the key before -- the optDelete. safeOptDeleteLookup :: DeleteMap t => (Value t -> (r, Bool)) -> Key t -> t -> Maybe (r, t) optDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> f t unsafeOptDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> f t safeOptDeleteF :: (DeleteMap t, Functor f) => (Value t -> f Bool) -> Key t -> t -> Maybe (f t) -- | Functions for doing inserts that don't fail on the keys being found -- but instead override existing values. class (InsertMap t, UpdateMap t) => UpsertMap t upsert :: UpsertMap t => Key t -> Value t -> t -> t upsertLookup :: UpsertMap t => Key t -> Value t -> t -> (Maybe (Value t), t) adsertF :: (UpsertMap t, Functor f) => (Maybe (Value t) -> f (Value t)) -> Key t -> t -> f t class (DeleteMap t, UpdateMap t) => UpleteMap t adlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t adleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) unsafeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t unsafeAdleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) maybeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> t safeAdlete :: UpleteMap t => (Value t -> Maybe (Value t)) -> Key t -> t -> Maybe t safeAdleteLookup :: UpleteMap t => (Value t -> (r, Maybe (Value t))) -> Key t -> t -> Maybe (r, t) adleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> f t unsafeAdleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> f t safeAdleteF :: (UpleteMap t, Functor f) => (Value t -> f (Maybe (Value t))) -> Key t -> t -> Maybe (f t) -- | AlterMap is a class that represents key-value mappings where -- one can do inserts, deletes, updates, pretty much everything you -- expect from a simple key/value store. class (UpsertMap t, UpleteMap t) => AlterMap t -- | alter f k x attempts to gets the value of the key k. -- -- If key k exists, as say it is v, it passes Just -- v to f. -- -- If key k does not exist, it passes Nothing to -- f. -- -- If the result of f is Just something, then -- alter either inserts or updates the key k, inserting -- if key k previously didn't exist and updating if it did. -- -- If the result of f is Nothing, and the key -- k did exist, we deleted it. -- -- Otherwise, if the result of f is Nothing, nd the key -- k did not exist, then do nothing and simply return the -- structure unmodified. alter :: AlterMap t => (Maybe (Value t) -> Maybe (Value t)) -> Key t -> t -> t -- | Like alter, but returns the value both before and after the -- alteration. alterLookup :: AlterMap t => (Maybe (Value t) -> (r, Maybe (Value t))) -> Key t -> t -> (r, t) alterF :: (AlterMap t, Functor f) => (Maybe (Value t) -> f (Maybe (Value t))) -> Key t -> t -> f t -- | For certain types like maps in the standard containers library that -- ships with GHC, the strict version of the data type: Map, and -- the lazy version of the data type: Map, are actually the exact -- same type. In this case, they're just reexports of the same type. -- -- That's fine when one has two separate modules with strict and lazy -- versions one can explicitly use, but the choice can't be automatic -- based on the type. -- -- As a result, there's no way one can tell whether to use strict or lazy -- functions on the data. Wrapping these types in either Strict or -- Lazy specifies how these types are intend to be worked on. -- -- By default however, if one doesn't wrap, the Strict version is -- used. newtype Strict t Strict :: t -> Strict t -- | See Strict documentation for a discussion of the Lazy -- wrapper. newtype Lazy t Lazy :: t -> Lazy t (!) :: LookupMap t => t -> Key t -> Value t