Datafix.MonoMap

A uniform interface for ordered maps that can be used to model monotone functions.

Documentation

class Foldable (MonoMap k) => MonoMapKey k where

Chooses an appropriate MonoMap for a given key type.

MonoMaps should all be ordered maps, which feature efficient variants of the lookupLT and lookupMin combinators. This unifies Data.Maybe, Data.IntMap.Strict, Data.Map.Strict and Data.POMap.Strict under a common type class, for which instances can delegate to the most efficient variant available.

Because of lookupLT, this class lends itself well to approximating monotone functions.

The default implementation delegates to POMap, so when there is no specially crafted map data-structure for your key type, all you need to do is to make sure it satisfies PartialOrd. Then you can do

>>> import Data.IntSet
>>> instance MonoMapKey IntSet

to make use of the default implementation.

Associated Types

type MonoMap k = (r :: * -> *) | r -> k

The particular ordered map implementation to use for the key type k.

The default implementation delegates to POMap.

Methods

empty :: MonoMap k v

empty :: MonoMap k v ~ POMap k v => MonoMap k v

singleton :: k -> v -> MonoMap k v

singleton :: MonoMap k v ~ POMap k v => k -> v -> MonoMap k v

insert :: k -> v -> MonoMap k v -> MonoMap k v

insert :: (MonoMap k v ~ POMap k v, PartialOrd k) => k -> v -> MonoMap k v -> MonoMap k v

delete :: k -> MonoMap k v -> MonoMap k v

delete :: (MonoMap k v ~ POMap k v, PartialOrd k) => k -> MonoMap k v -> MonoMap k v

lookup :: k -> MonoMap k v -> Maybe v

lookup :: (MonoMap k v ~ POMap k v, PartialOrd k) => k -> MonoMap k v -> Maybe v

lookupLT :: k -> MonoMap k v -> [(k, v)]

Key point of this interface! Note that it returns a list of lower bounds, to account for the PartialOrd case.

lookupLT :: (MonoMap k v ~ POMap k v, PartialOrd k) => k -> MonoMap k v -> [(k, v)]

Key point of this interface! Note that it returns a list of lower bounds, to account for the PartialOrd case.

lookupMin :: MonoMap k v -> [(k, v)]

lookupMin :: (MonoMap k v ~ POMap k v, PartialOrd k) => MonoMap k v -> [(k, v)]

difference :: MonoMap k a -> MonoMap k b -> MonoMap k a

difference :: (MonoMap k a ~ POMap k a, MonoMap k b ~ POMap k b, PartialOrd k) => MonoMap k a -> MonoMap k b -> MonoMap k a

keys :: MonoMap k a -> [k]

keys :: MonoMap k v ~ POMap k v => MonoMap k v -> [k]

insertWith :: (v -> v -> v) -> k -> v -> MonoMap k v -> MonoMap k v

insertWith :: (MonoMap k v ~ POMap k v, PartialOrd k) => (v -> v -> v) -> k -> v -> MonoMap k v -> MonoMap k v

insertLookupWithKey :: (k -> v -> v -> v) -> k -> v -> MonoMap k v -> (Maybe v, MonoMap k v)

insertLookupWithKey :: (MonoMap k v ~ POMap k v, PartialOrd k) => (k -> v -> v -> v) -> k -> v -> MonoMap k v -> (Maybe v, MonoMap k v)

updateLookupWithKey :: (k -> v -> Maybe v) -> k -> MonoMap k v -> (Maybe v, MonoMap k v)

updateLookupWithKey :: (MonoMap k v ~ POMap k v, PartialOrd k) => (k -> v -> Maybe v) -> k -> MonoMap k v -> (Maybe v, MonoMap k v)

alter :: (Maybe v -> Maybe v) -> k -> MonoMap k v -> MonoMap k v

alter :: (MonoMap k v ~ POMap k v, PartialOrd k) => (Maybe v -> Maybe v) -> k -> MonoMap k v -> MonoMap k v

adjust :: (v -> v) -> k -> MonoMap k v -> MonoMap k v

adjust :: (MonoMap k v ~ POMap k v, PartialOrd k) => (v -> v) -> k -> MonoMap k v -> MonoMap k v

Instances

MonoMapKey Int

Delegates to IntMap.

Associated Types

type MonoMap Int = (r :: * -> *)

Methods

empty :: MonoMap Int v

singleton :: Int -> v -> MonoMap Int v

insert :: Int -> v -> MonoMap Int v -> MonoMap Int v

delete :: Int -> MonoMap Int v -> MonoMap Int v

lookup :: Int -> MonoMap Int v -> Maybe v

lookupLT :: Int -> MonoMap Int v -> [(Int, v)]

lookupMin :: MonoMap Int v -> [(Int, v)]

difference :: MonoMap Int a -> MonoMap Int b -> MonoMap Int a

keys :: MonoMap Int a -> [Int]

insertWith :: (v -> v -> v) -> Int -> v -> MonoMap Int v -> MonoMap Int v

insertLookupWithKey :: (Int -> v -> v -> v) -> Int -> v -> MonoMap Int v -> (Maybe v, MonoMap Int v)

updateLookupWithKey :: (Int -> v -> Maybe v) -> Int -> MonoMap Int v -> (Maybe v, MonoMap Int v)

alter :: (Maybe v -> Maybe v) -> Int -> MonoMap Int v -> MonoMap Int v

adjust :: (v -> v) -> Int -> MonoMap Int v -> MonoMap Int v

MonoMapKey ()

Delegates to Maybe.

Associated Types

type MonoMap () = (r :: * -> *)

Methods

empty :: MonoMap () v

singleton :: () -> v -> MonoMap () v

insert :: () -> v -> MonoMap () v -> MonoMap () v

delete :: () -> MonoMap () v -> MonoMap () v

lookup :: () -> MonoMap () v -> Maybe v

lookupLT :: () -> MonoMap () v -> [((), v)]

lookupMin :: MonoMap () v -> [((), v)]

difference :: MonoMap () a -> MonoMap () b -> MonoMap () a

keys :: MonoMap () a -> [()]

insertWith :: (v -> v -> v) -> () -> v -> MonoMap () v -> MonoMap () v

insertLookupWithKey :: (() -> v -> v -> v) -> () -> v -> MonoMap () v -> (Maybe v, MonoMap () v)

updateLookupWithKey :: (() -> v -> Maybe v) -> () -> MonoMap () v -> (Maybe v, MonoMap () v)

alter :: (Maybe v -> Maybe v) -> () -> MonoMap () v -> MonoMap () v

adjust :: (v -> v) -> () -> MonoMap () v -> MonoMap () v