Copyright	(c) Andrey Mulik 2019
License	BSD-style
Maintainer	work.a.mulik@gmail.com
Portability	non-portable (GHC extensions)
Safe Haskell	Safe
Language	Haskell2010

SDP.Map

Contents

Exports
Map

Description

SDP.Map provides Map - class of immutable associative arrays.

Synopsis

module SDP.Set
class Nullable map => Map map key e | map -> key, map -> e where
- assocs :: map -> [(key, e)]
- toMap :: [(key, e)] -> map
- toMap' :: e -> [(key, e)] -> map
- insert' :: key -> e -> map -> map
- delete' :: key -> map -> map
- member' :: key -> map -> Bool
- (//) :: map -> [(key, e)] -> map
- (.!) :: map -> key -> e
- (!) :: map -> key -> e
- (!?) :: map -> key -> Maybe e
- filter' :: (key -> e -> Bool) -> map -> map
- union' :: Ord key => (e -> e -> e) -> map -> map -> map
- difference' :: Ord key => (e -> e -> Maybe e) -> map -> map -> map
- intersection' :: Ord key => (e -> e -> e) -> map -> map -> map
- update :: map -> (key -> e -> e) -> map
- lookupLT' :: Ord key => key -> map -> Maybe (key, e)
- lookupGT' :: Ord key => key -> map -> Maybe (key, e)
- lookupLE' :: Ord key => key -> map -> Maybe (key, e)
- lookupGE' :: Ord key => key -> map -> Maybe (key, e)
- keys :: map -> [key]
- (.$) :: (e -> Bool) -> map -> Maybe key
- (*$) :: (e -> Bool) -> map -> [key]
- kfoldr :: (key -> e -> b -> b) -> b -> map -> b
- kfoldl :: (key -> b -> e -> b) -> b -> map -> b
- kfoldr' :: (key -> e -> b -> b) -> b -> map -> b
- kfoldl' :: (key -> b -> e -> b) -> b -> map -> b
type Map1 map key e = Map (map e) key e
type Map2 map key e = Map (map key e) key e

Exports

module SDP.Set

Map

class Nullable map => Map map key e | map -> key, map -> e where Source #

Map is a class of dictionaries, simple associative arrays with an arbitrary (implementation-dependent) key.

In the current implementation, Map (since sdp-0.2) is a superclass of Indexed. Map provides a set of operations on associative arrays that aren't specific to Linear data structures and aren't limited by the Bordered context (doesn't restrict key type).

Minimal complete definition

toMap', ((.!) | (!?))

Methods

assocs :: map -> [(key, e)] Source #

Returns list of associations (index, element).

default assocs :: (Bordered map key, Linear map e) => map -> [(key, e)] Source #

toMap :: [(key, e)] -> map Source #

A less specific version of "SDP.Indexed.Indexed.assoc" that creates a new associative array. For Linear structures without gaps, it may be less effective.

Z // ascs = toMap -- forall ascs

toMap' :: e -> [(key, e)] -> map Source #

Strict version of toMap with default value.

Note that the default value is set only for elements included in the range of the created structure and will not be set for values outside its range (when expanding, concatenating, etc.) for most structures since they don't store it.

insert' :: key -> e -> map -> map Source #

insert' key e map inserts e with key to map. If map already contains an element with key, the element will be overwritten.

If map doesn't allow gaps, then the missing elements should be filled with default values.

default insert' :: Bordered map key => key -> e -> map -> map Source #

delete' :: key -> map -> map Source #

delete' removes element with given key.

If the structure has boundaries, when removed from the beginning (end), they should change accordingly. If the structure doesn't allow gaps, then when removed from the middle, the actual value should be replaced with the default value.

default delete' :: Eq key => key -> map -> map Source #

member' :: key -> map -> Bool Source #

member' key map checks if key in map.

default member' :: Bordered map key => key -> map -> Bool Source #

(//) :: map -> [(key, e)] -> map Source #

Update elements of immutable structure (by copying).

(.!) :: map -> key -> e infixl 9 Source #

(.!) is unsafe reader, can be faster (!) by skipping checks.

(!) :: map -> key -> e infixl 9 Source #

(!) is well-safe reader, may throw IndexException.

default (!) :: Bordered map key => map -> key -> e Source #

(!?) :: map -> key -> Maybe e infixl 9 Source #

(!?) is completely safe, but very boring function.

filter' :: (key -> e -> Bool) -> map -> map Source #

Filter with key.

union' :: Ord key => (e -> e -> e) -> map -> map -> map Source #

union' is groupSetWith for maps but works with real groups of elements, not with consequentive equal elements.

union' merges/chooses elements with equal keys from two maps.

difference' :: Ord key => (e -> e -> Maybe e) -> map -> map -> map Source #

difference' f mx my applies comb to values with equal keys. If f x y (where (k1, x) <- mx, (k2, y) <- my, k1 == k2) is Nothing, element isn't included to result map.

Note that difference' is poorer than a similar functions in containers.

intersection' :: Ord key => (e -> e -> e) -> map -> map -> map Source #

intersection' f mx my combines elements of intersection' by f: if isJust (f x y) (where (k1, x) <- mx, (k2, y) <- my, k1 == k2), then element is added to result map.

update :: map -> (key -> e -> e) -> map Source #

Update function, by default uses (!) and may throw IndexException.

lookupLT' :: Ord key => key -> map -> Maybe (key, e) Source #

lookupLT' k map finds pair (key, value) with smallest key, where key < k (if any). k may not be a map element.

lookupGT' :: Ord key => key -> map -> Maybe (key, e) Source #

lookupGT' k map finds pair (key, value) with greatest key, where key > k (if any). k may not be a map element.

lookupLE' :: Ord key => key -> map -> Maybe (key, e) Source #

lookupLE' k map finds pair (key, value) with smallest key, where key <= k (if any). If k is a map element, returns (k, e).

lookupGE' :: Ord key => key -> map -> Maybe (key, e) Source #

lookupGE' k map finds pair (key, value) with key, where key >= k (if any).

keys :: map -> [key] Source #

Returns list of map keys.

(.$) :: (e -> Bool) -> map -> Maybe key Source #

Searches the key of first matching element.

(*$) :: (e -> Bool) -> map -> [key] Source #

Searches the keys of all matching elements.

kfoldr :: (key -> e -> b -> b) -> b -> map -> b Source #

kfoldr is foldr with key.

kfoldl :: (key -> b -> e -> b) -> b -> map -> b Source #

kfoldl is foldl with key.

kfoldr' :: (key -> e -> b -> b) -> b -> map -> b Source #

kfoldr' is strict version of kfoldr.

kfoldl' :: (key -> b -> e -> b) -> b -> map -> b Source #

kfoldl' is strict version of kfoldl.

Instances

Instances details

Map [e] Int e Source #
Instance details Defined in SDP.Map Methods assocs :: [e] -> [(Int, e)] Source # toMap :: [(Int, e)] -> [e] Source # toMap' :: e -> [(Int, e)] -> [e] Source # insert' :: Int -> e -> [e] -> [e] Source # delete' :: Int -> [e] -> [e] Source # member' :: Int -> [e] -> Bool Source # (//) :: [e] -> [(Int, e)] -> [e] Source # (.!) :: [e] -> Int -> e Source # (!) :: [e] -> Int -> e Source # (!?) :: [e] -> Int -> Maybe e Source # filter' :: (Int -> e -> Bool) -> [e] -> [e] Source # union' :: (e -> e -> e) -> [e] -> [e] -> [e] Source # difference' :: (e -> e -> Maybe e) -> [e] -> [e] -> [e] Source # intersection' :: (e -> e -> e) -> [e] -> [e] -> [e] Source # update :: [e] -> (Int -> e -> e) -> [e] Source # lookupLT' :: Int -> [e] -> Maybe (Int, e) Source # lookupGT' :: Int -> [e] -> Maybe (Int, e) Source # lookupLE' :: Int -> [e] -> Maybe (Int, e) Source # lookupGE' :: Int -> [e] -> Maybe (Int, e) Source # keys :: [e] -> [Int] Source # (.$) :: (e -> Bool) -> [e] -> Maybe Int Source # (*$) :: (e -> Bool) -> [e] -> [Int] Source # kfoldr :: (Int -> e -> b -> b) -> b -> [e] -> b Source # kfoldl :: (Int -> b -> e -> b) -> b -> [e] -> b Source # kfoldr' :: (Int -> e -> b -> b) -> b -> [e] -> b Source # kfoldl' :: (Int -> b -> e -> b) -> b -> [e] -> b Source #
Unboxed e => Map (SBytes# e) Int e Source #
Instance details Defined in SDP.Prim.SBytes Methods assocs :: SBytes# e -> [(Int, e)] Source # toMap :: [(Int, e)] -> SBytes# e Source # toMap' :: e -> [(Int, e)] -> SBytes# e Source # insert' :: Int -> e -> SBytes# e -> SBytes# e Source # delete' :: Int -> SBytes# e -> SBytes# e Source # member' :: Int -> SBytes# e -> Bool Source # (//) :: SBytes# e -> [(Int, e)] -> SBytes# e Source # (.!) :: SBytes# e -> Int -> e Source # (!) :: SBytes# e -> Int -> e Source # (!?) :: SBytes# e -> Int -> Maybe e Source # filter' :: (Int -> e -> Bool) -> SBytes# e -> SBytes# e Source # union' :: (e -> e -> e) -> SBytes# e -> SBytes# e -> SBytes# e Source # difference' :: (e -> e -> Maybe e) -> SBytes# e -> SBytes# e -> SBytes# e Source # intersection' :: (e -> e -> e) -> SBytes# e -> SBytes# e -> SBytes# e Source # update :: SBytes# e -> (Int -> e -> e) -> SBytes# e Source # lookupLT' :: Int -> SBytes# e -> Maybe (Int, e) Source # lookupGT' :: Int -> SBytes# e -> Maybe (Int, e) Source # lookupLE' :: Int -> SBytes# e -> Maybe (Int, e) Source # lookupGE' :: Int -> SBytes# e -> Maybe (Int, e) Source # keys :: SBytes# e -> [Int] Source # (.$) :: (e -> Bool) -> SBytes# e -> Maybe Int Source # (*$) :: (e -> Bool) -> SBytes# e -> [Int] Source # kfoldr :: (Int -> e -> b -> b) -> b -> SBytes# e -> b Source # kfoldl :: (Int -> b -> e -> b) -> b -> SBytes# e -> b Source # kfoldr' :: (Int -> e -> b -> b) -> b -> SBytes# e -> b Source # kfoldl' :: (Int -> b -> e -> b) -> b -> SBytes# e -> b Source #
Map (SArray# e) Int e Source #
Instance details Defined in SDP.Prim.SArray Methods assocs :: SArray# e -> [(Int, e)] Source # toMap :: [(Int, e)] -> SArray# e Source # toMap' :: e -> [(Int, e)] -> SArray# e Source # insert' :: Int -> e -> SArray# e -> SArray# e Source # delete' :: Int -> SArray# e -> SArray# e Source # member' :: Int -> SArray# e -> Bool Source # (//) :: SArray# e -> [(Int, e)] -> SArray# e Source # (.!) :: SArray# e -> Int -> e Source # (!) :: SArray# e -> Int -> e Source # (!?) :: SArray# e -> Int -> Maybe e Source # filter' :: (Int -> e -> Bool) -> SArray# e -> SArray# e Source # union' :: (e -> e -> e) -> SArray# e -> SArray# e -> SArray# e Source # difference' :: (e -> e -> Maybe e) -> SArray# e -> SArray# e -> SArray# e Source # intersection' :: (e -> e -> e) -> SArray# e -> SArray# e -> SArray# e Source # update :: SArray# e -> (Int -> e -> e) -> SArray# e Source # lookupLT' :: Int -> SArray# e -> Maybe (Int, e) Source # lookupGT' :: Int -> SArray# e -> Maybe (Int, e) Source # lookupLE' :: Int -> SArray# e -> Maybe (Int, e) Source # lookupGE' :: Int -> SArray# e -> Maybe (Int, e) Source # keys :: SArray# e -> [Int] Source # (.$) :: (e -> Bool) -> SArray# e -> Maybe Int Source # (*$) :: (e -> Bool) -> SArray# e -> [Int] Source # kfoldr :: (Int -> e -> b -> b) -> b -> SArray# e -> b Source # kfoldl :: (Int -> b -> e -> b) -> b -> SArray# e -> b Source # kfoldr' :: (Int -> e -> b -> b) -> b -> SArray# e -> b Source # kfoldl' :: (Int -> b -> e -> b) -> b -> SArray# e -> b Source #
Indexed1 rep Int e => Map (AnyChunks rep e) Int e Source #
Instance details Defined in SDP.Templates.AnyChunks Methods assocs :: AnyChunks rep e -> [(Int, e)] Source # toMap :: [(Int, e)] -> AnyChunks rep e Source # toMap' :: e -> [(Int, e)] -> AnyChunks rep e Source # insert' :: Int -> e -> AnyChunks rep e -> AnyChunks rep e Source # delete' :: Int -> AnyChunks rep e -> AnyChunks rep e Source # member' :: Int -> AnyChunks rep e -> Bool Source # (//) :: AnyChunks rep e -> [(Int, e)] -> AnyChunks rep e Source # (.!) :: AnyChunks rep e -> Int -> e Source # (!) :: AnyChunks rep e -> Int -> e Source # (!?) :: AnyChunks rep e -> Int -> Maybe e Source # filter' :: (Int -> e -> Bool) -> AnyChunks rep e -> AnyChunks rep e Source # union' :: (e -> e -> e) -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e Source # difference' :: (e -> e -> Maybe e) -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e Source # intersection' :: (e -> e -> e) -> AnyChunks rep e -> AnyChunks rep e -> AnyChunks rep e Source # update :: AnyChunks rep e -> (Int -> e -> e) -> AnyChunks rep e Source # lookupLT' :: Int -> AnyChunks rep e -> Maybe (Int, e) Source # lookupGT' :: Int -> AnyChunks rep e -> Maybe (Int, e) Source # lookupLE' :: Int -> AnyChunks rep e -> Maybe (Int, e) Source # lookupGE' :: Int -> AnyChunks rep e -> Maybe (Int, e) Source # keys :: AnyChunks rep e -> [Int] Source # (.$) :: (e -> Bool) -> AnyChunks rep e -> Maybe Int Source # (*$) :: (e -> Bool) -> AnyChunks rep e -> [Int] Source # kfoldr :: (Int -> e -> b -> b) -> b -> AnyChunks rep e -> b Source # kfoldl :: (Int -> b -> e -> b) -> b -> AnyChunks rep e -> b Source # kfoldr' :: (Int -> e -> b -> b) -> b -> AnyChunks rep e -> b Source # kfoldl' :: (Int -> b -> e -> b) -> b -> AnyChunks rep e -> b Source #
(Index i, Indexed1 rep Int e) => Map (AnyBorder rep i e) i e Source #
Instance details Defined in SDP.Templates.AnyBorder Methods assocs :: AnyBorder rep i e -> [(i, e)] Source # toMap :: [(i, e)] -> AnyBorder rep i e Source # toMap' :: e -> [(i, e)] -> AnyBorder rep i e Source # insert' :: i -> e -> AnyBorder rep i e -> AnyBorder rep i e Source # delete' :: i -> AnyBorder rep i e -> AnyBorder rep i e Source # member' :: i -> AnyBorder rep i e -> Bool Source # (//) :: AnyBorder rep i e -> [(i, e)] -> AnyBorder rep i e Source # (.!) :: AnyBorder rep i e -> i -> e Source # (!) :: AnyBorder rep i e -> i -> e Source # (!?) :: AnyBorder rep i e -> i -> Maybe e Source # filter' :: (i -> e -> Bool) -> AnyBorder rep i e -> AnyBorder rep i e Source # union' :: (e -> e -> e) -> AnyBorder rep i e -> AnyBorder rep i e -> AnyBorder rep i e Source # difference' :: (e -> e -> Maybe e) -> AnyBorder rep i e -> AnyBorder rep i e -> AnyBorder rep i e Source # intersection' :: (e -> e -> e) -> AnyBorder rep i e -> AnyBorder rep i e -> AnyBorder rep i e Source # update :: AnyBorder rep i e -> (i -> e -> e) -> AnyBorder rep i e Source # lookupLT' :: i -> AnyBorder rep i e -> Maybe (i, e) Source # lookupGT' :: i -> AnyBorder rep i e -> Maybe (i, e) Source # lookupLE' :: i -> AnyBorder rep i e -> Maybe (i, e) Source # lookupGE' :: i -> AnyBorder rep i e -> Maybe (i, e) Source # keys :: AnyBorder rep i e -> [i] Source # (.$) :: (e -> Bool) -> AnyBorder rep i e -> Maybe i Source # (*$) :: (e -> Bool) -> AnyBorder rep i e -> [i] Source # kfoldr :: (i -> e -> b -> b) -> b -> AnyBorder rep i e -> b Source # kfoldl :: (i -> b -> e -> b) -> b -> AnyBorder rep i e -> b Source # kfoldr' :: (i -> e -> b -> b) -> b -> AnyBorder rep i e -> b Source # kfoldl' :: (i -> b -> e -> b) -> b -> AnyBorder rep i e -> b Source #

type Map1 map key e = Map (map e) key e Source #

Kind (* -> *) Map structure.

type Map2 map key e = Map (map key e) key e Source #

Kind (* -> * -> *) Map structure.