SML/NJ Library Manual

The ORD_MAP signature

Synopsis

signature ORD_MAP
structure IntBinaryMap :> ORD_MAP
structure IntListMap :> ORD_MAP


The ORD_MAP signature provides an abstract description of applicative-style maps on a linearly ordered key type.

Interface

structure Key : ORD_KEY
type 'a map
val empty : 'a map
val insert : ('a map * Key.ord_key * 'a) -> 'a map
val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map
val find : ('a map * Key.ord_key) -> 'a option
val remove : ('a map * Key.ord_key) -> ('a map * 'a)
val numItems : 'a map -> int
val listItems : 'a map -> 'a list
val listItemsi : 'a map -> (Key.ord_key * 'a) list
val collate : (('a * 'a) -> order) -> ('a map * 'a map) -> order
val unionWith : (('a * 'a) -> 'a) -> ('a map * 'a map) -> 'a map
val unionWithi : ((Key.ord_key * 'a * 'a) -> 'a) -> ('a map * 'a map) -> 'a map
val intersectWith : (('a * 'b) -> 'c) -> ('a map * 'b map) -> 'c map
val intersectWithi : ((Key.ord_key * 'a * 'b) -> 'c) -> ('a map * 'b map) -> 'c map
val app : ('a -> unit) -> 'a map -> unit
val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit
val map : ('a -> 'b) -> 'a map -> 'b map
val mapi : ((Key.ord_key * 'a) -> 'b) -> 'a map -> 'b map
val foldl : (('a * 'b) -> 'b) -> 'b -> 'a map -> 'b
val foldli : ((Key.ord_key * 'a * 'b) -> 'b) -> 'b -> 'a map -> 'b
val foldr : (('a * 'b) -> 'b) -> 'b -> 'a map -> 'b
val foldri : ((Key.ord_key * 'a * 'b) -> 'b) -> 'b -> 'a map -> 'b
val filter : ('a -> bool) -> 'a map -> 'a map
val filteri : ((Key.ord_key * 'a) -> bool) -> 'a map -> 'a map
val mapPartial : ('a -> 'b option) -> 'a map -> 'b map
val mapPartiali : ((Key.ord_key * 'a) -> 'b option) -> 'a map -> 'b map


Description

type 'a map

val empty

The empty map.

insert (ma, ok, a)

insert' ((ok, a), ma)

creates a new map by inserting the key-value pair into ma.

find (ma, ok)

looks for an item in ma keyed by ok. It returns the item if it finds it; otherwise, returns NONE.

remove (ma, ok)

removes an item from ma corresponding to the key ok. If found, the resulting map and item are returned. Raises NotFound if no such item exists.

numItems ma

returns the number of items in the map.

listItems ma

listItemsi ma

return a list of the items in the map, ordered by increasing key. The second form also returns the key.

collate f

returns an ordering on maps, given an ordering on the maps' range.

unionWith f (ma, ma2)

unionWithi f (ma, ma2)

returns a map that is the union of the maps ma and ma2. The first argument is used to define the map on elements that are in the domain of both maps. In the second form, the function takes the shared key as well as the two range values.

intersectWith f (ma, ma2)

intersectWithi f (ma, ma2)

returns a map defined on the intersection of the domains of the maps ma and ma2. The function f is used to define the range. Specifically, if (k,u) is in ma and (k,v) is in ma2, the new map contains (k,f(u,v)) (or (k,f(k,u,v)), in the second case).

app f ma

appi f ma

applies the function f to the items in the map in increasing order of the key. These are respectively equivalent to:

          List.app f (listItems ma)
          List.app f (listItemsi ma)
          

map f ma

mapi f ma

creates a new map by applying the function f to the elements of the old map ma. These are respectively equivalent to:

          List.foldl (fn((k,v),m) => insert(m,k,f v)) empty (listItemsi ma)
          List.foldl (fn((k,v),m) => insert(m,k,f(k,v))) empty (listItemsi ma)
          

foldl f a ma

foldli f a ma

applies the folding function f to the entries of ma in increasing order. These are respectively equivalent to:

          List.foldl f a (listItems ma)
          List.foldl (fn((k,v),b) => f(k,v,b)) a (listItemsi ma)
          

foldr f a ma

foldri f a ma

applies the folding function f to the entries of ma in decreasing order. These are respectively equivalent to:

          List.foldr f a (listItems ma)
          List.foldr (fn((k,v),b) => f(k,v,b)) a (listItemsi ma)
          

filter f ma

filteri f ma

creates a new map containing only those elements of ma that satisfy the predicate f. These are equivalent to:

          List.foldl insert' empty (List.filter (fn(k,v) => f v) (listItemsi ma))
          List.foldl insert' empty (List.filter f (listItemsi ma))
          

mapPartial f ma

mapPartiali f ma

creates a new map by applying the partial function f to the map ma in increasing key order. The function mapPartiali can be implemented as:

          fun mapPartiali f ma = let
                fun f' (key,value) = case f (key,value)
                   of NONE => NONE
                    | SOME v => SOME(key,v)
                val items = List.mapPartial f' (listItemsi ma)
                in
                  List.foldl insert' empty items
                end
          

The function mapPartial is equivalent to:

          fun mapPartial f ma = mapPartiali (fn (_, item) => f item) ma
          

See Also

ORD_SET, ORD_KEY, BinaryMapFn, SplayMapFn, ListMapFn

Last Modified June 10, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies