Copyright | (c) Andrey Mulik 2019 |
---|---|

License | BSD-style |

Maintainer | work.a.mulik@gmail.com |

Portability | non-portable (GHC extensions) |

Safe Haskell | Safe |

Language | Haskell2010 |

## 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).

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

Returns list of associations `(index, element)`

.

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 #

inserts `insert'`

key e map`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.

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.

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

checks if `member'`

key map`key`

in `map`

.

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

Update elements of immutable structure (by copying).

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

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

`(`

is well-safe reader, may `!`

)`throw`

`IndexException`

.

(!?) :: 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 #

applies `difference'`

f mx my`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 #

combines elements of `intersection'`

f mx my`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).

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 #

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

#### Instances

Map [e] Int e Source # | |

Defined in SDP.Map 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 # (.$) :: (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 # | |

Unboxed e => Map (SBytes# e) Int e Source # | |

Defined in SDP.Prim.SBytes 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 # | |

Defined in SDP.Prim.SArray 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 # | |

Defined in SDP.Templates.AnyChunks 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 # | |

Defined in SDP.Templates.AnyBorder 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 # |