# 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

[ Top | Parent | Contents | Index | Root ]

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