std.ordmap

Maps from keys to values, by an order of the keys: a balanced (AVL) tree, so a lookup, an insertion or a deletion takes as many steps as the log of the size. The keys’ order is their type’s Order, found as an instance argument is (the prelude’s of Int, String, Rune, …, or one of your own), and a map must always be given the same one. Import it by a name, import std.ordmap as OrdMap, as the prelude has a map and a lookup. The map comes first: OrdMap.insert m k v, OrdMap.lookup m k.

import std.ordmap as OrdMap

-- | how many times each word appears
-- | >>> OrdMap.toList (counts ["a", "b", "a"])
-- | [MkPair "a" 2, MkPair "b" 1]
counts : List String -> OrdMap.OrdMap String Int
counts ws = List.foldl (\m w -> OrdMap.update m w 1 (\new old -> new + old)) OrdMap.empty ws

OrdMap

data OrdMap k v = Tip | Bin Int k v (OrdMap k v) (OrdMap k v)

A map, as a tree: each node with its height, a key, its value, and the smaller keys left, the greater right.

empty

empty : {k v : Type} -> OrdMap k v

The map of no keys.

singleton

singleton : {k v : Type} -> k -> v -> OrdMap k v

The map of one key, k, bound to v.

height

height : {k v : Type} -> OrdMap k v -> Int

node

node : {k v : Type} -> k -> v -> OrdMap k v -> OrdMap k v -> OrdMap k v

rotated

rotated : {k v : Type} -> OrdMap k v -> OrdMap k v

heightOver

heightOver : Int -> Int -> Int

nodeOf

nodeOf : {k v : Type} -> Int -> k -> v -> OrdMap k v -> OrdMap k v -> OrdMap k v

insert

insert : {k v : Type} -> {{ord : Order k}} -> OrdMap k v -> k -> v -> OrdMap k v

m with k bound to v (instead of what it was, if it was).

lookup

lookup : {k v : Type} -> {{ord : Order k}} -> OrdMap k v -> k -> Maybe v

What k is bound to, if it is.

>>> lookup (insert empty "a" 1) "a"
Just 1

member

member : {k v : Type} -> {{ord : Order k}} -> OrdMap k v -> k -> Bool

Whether k is bound.

findMin

findMin : {k v : Type} -> OrdMap k v -> Maybe (k, v)

The least key, and its value, if the map is not empty.

>>> findMin (insert (insert empty 2 "b") 1 "a")
Just (MkPair 1 "a")

deleteMin

deleteMin : {k v : Type} -> OrdMap k v -> OrdMap k v

The map without its least key (as it was, if it is empty).

leastSplit

leastSplit : {k v : Type} -> OrdMap k v -> (OrdMap k v, OrdMap k v)

glue

glue : {k v : Type} -> OrdMap k v -> OrdMap k v -> OrdMap k v

delete

delete : {k v : Type} -> {{ord : Order k}} -> OrdMap k v -> k -> OrdMap k v

The map without k (as it was, if k was not in it).

toList

toList : {k v : Type} -> OrdMap k v -> List (k, v)

The keys and their values, the keys in order.

leftSpine

leftSpine : {k v : Type} -> OrdMap k v -> List (OrdMap k v) -> List (OrdMap k v)

nextOfSpine

nextOfSpine : {k v : Type}
            -> List (OrdMap k v)
            -> Maybe (k, v, List (OrdMap k v))

instanceIterateOrdMap

instance instanceIterateOrdMap : {k v : Type} -> Iterate (OrdMap k v)

A map, each key and its value in the keys’ order: for p in m goes through it by a stack of the nodes yet to be reached, built as it goes.

insertAll

insertAll : {k v : Type}
          -> {{ord : Order k}}
          -> OrdMap k v
          -> List (k, v)
          -> OrdMap k v

fromList

fromList : {k v : Type} -> {{ord : Order k}} -> List (k, v) -> OrdMap k v

The map of the pairs, a later one’s value for a key twice.

update

update : {k v : Type}
       -> {{ord : Order k}}
       -> OrdMap k v
       -> k
       -> v
       -> (v -> v -> v)
       -> OrdMap k v

The map with k bound to v, or, where it is bound, to f v old (Haskell’s insertWith): a value changed in one walk down the tree, where a lookup and an insert take two.

>>> toList (update (fromList [MkPair "a" 2, MkPair "b" 5]) "a" 1 (\new old -> new + old))
Cons (MkPair "a" 3) (Cons (MkPair "b" 5) Nil)
>>> toList (update empty 7 1 (\new old -> new + old))
Cons (MkPair 7 1) Nil

planted

planted : {k v : Type} -> k -> Maybe v -> OrdMap k v

replanted

replanted : {k v : Type}
          -> Int
          -> k
          -> Maybe v
          -> OrdMap k v
          -> OrdMap k v
          -> OrdMap k v

alter

alter : {k v : Type}
      -> {{ord : Order k}}
      -> OrdMap k v
      -> k
      -> (Maybe v -> Maybe v)
      -> OrdMap k v

The map with k bound as f says, given what it is bound to, if it is: to f’s value, or (Nothing) to none (Haskell’s alter).

>>> toList (alter (fromList [MkPair "a" 2]) "a" (\old -> Just (maybe 1 (\n -> n + 1) old)))
Cons (MkPair "a" 3) Nil
>>> toList (alter (fromList [MkPair 1 "one", MkPair 2 "two"]) 1 (\old -> Nothing))
Cons (MkPair 2 "two") Nil
>>> toList (alter (fromList [MkPair 1 "one"]) 3 (\old -> Just "three"))
Cons (MkPair 1 "one") (Cons (MkPair 3 "three") Nil)

keys

keys : {k v : Type} -> OrdMap k v -> List k

The keys, in order.

values

values : {k v : Type} -> OrdMap k v -> List v

The values, in their keys’ order.

size

size : {k v : Type} -> OrdMap k v -> Int

How many keys are bound.

mapValues

mapValues : {k v w : Type} -> (v -> w) -> OrdMap k v -> OrdMap k w

Each value, f of it.

union

union : {k v : Type}
      -> {{ord : Order k}}
      -> OrdMap k v
      -> OrdMap k v
      -> OrdMap k v

The keys of both; a key of both with its value in a.

null

null : {k v : Type} -> OrdMap k v -> Bool

Whether it has no keys.

>>> List.map null [empty, singleton 1 "a"]
Cons True (Cons False Nil)

findMax

findMax : {k v : Type} -> OrdMap k v -> Maybe (k, v)

The greatest key and its value, if there is one.

>>> findMax (fromList [MkPair 2 "b", MkPair 3 "c", MkPair 1 "a"])
Just (MkPair 3 "c")

deleteMax

deleteMax : {k v : Type} -> OrdMap k v -> OrdMap k v

The map without its greatest key (as it was, if it is empty).

>>> keys (deleteMax (fromList [MkPair 2 "b", MkPair 3 "c", MkPair 1 "a"]))
Cons 1 (Cons 2 Nil)

remove

remove : {k v : Type}
       -> {{ord : Order k}}
       -> OrdMap k v
       -> k
       -> (Maybe v, OrdMap k v)

What k was bound to, if it was, and the map without it, as std.hashmap’s remove.

>>> remove (fromList [MkPair 1 "a", MkPair 2 "b"]) 1
MkPair (Just "a") (Bin 1 2 "b" Tip Tip)

foldl

foldl : {k v b : Type} -> (b -> k -> v -> b) -> b -> OrdMap k v -> b

Each key and its value, in the keys’ order, into z.

>>> foldl (\acc k v -> acc ^ debug k ^ v) "" (fromList [MkPair 2 "b", MkPair 1 "a"])
"1a2b"

foldr

foldr : {k v b : Type} -> (k -> v -> b -> b) -> b -> OrdMap k v -> b

Each key and its value, from the greatest key: f k1 v1 (f k2 v2 (… z)).

>>> foldr (\k v acc -> acc ^ debug k ^ v) "" (fromList [MkPair 2 "b", MkPair 1 "a"])
"2b1a"

balanced

balanced : {k v : Type} -> OrdMap k v -> Bool

ascending

ascending : {k : Type} -> {{ord : Order k}} -> List k -> Bool

valid

valid : {k v : Type} -> {{ord : Order k}} -> OrdMap k v -> Bool

Whether it is balanced and in order: every node’s subtrees differ in height by one at most, its height is right, and its keys go up.