---
name: "Map.Make"
section: "3o"
platform: "linux"
package: "ocaml"
version: "5.5.0-1"
release: "Arch Linux 2026-11-01"
platforms: ["linux"]
url: "https://new.carta.tech/Map.Make"
---

# Map.Make(3o)

Functor building an implementation of the map structure given a totally ordered type.

## NAME

Map.Make - Functor building an implementation of the map structure given a totally ordered type.

## Module

Module   Map.Make

## Documentation

Module **Make**\
  :  **(Ord : OrderedType) -\> sig end**

Functor building an implementation of the map structure given a totally ordered type.

**Parameters:**

"Ord"

**Map.OrderedType**

### Maps

*type key*

The type of the map keys.

*type* **!+'a** *t*

The type of maps from type  **key** to type  **'a** .

*val empty* :  **'a t**

The empty map.

*val add* :  **key -\> 'a -\> 'a t -\> 'a t**

**add key data m** returns a map containing the same bindings as **m** , plus a binding of  **key** to  **data** . If  **key** was already bound in  **m** to a value that is physically equal to  **data** , **m** is returned unchanged (the result of the function is then physically equal to  **m** ). Otherwise, the previous binding of  **key** in  **m** disappears.

**Before4.03** Physical equality was not ensured.

*val add\_to\_list* :  **key -\> 'a -\> 'a list t -\> 'a list t**

**add\_to\_list key data m** is  **m** with  **key** mapped to  **l** such that  **l** is  **data :: Map.find key m** if  **key** was bound in **m** and  **\[data\]** otherwise.

**Since** 5.1

*val update* :  **key -\> ('a option -\> 'a option) -\> 'a t -\> 'a t**

**update key f m** returns a map containing the same bindings as **m** , except for the binding of  **key** . Depending on the value of **y** where  **y** is  **f (find\_opt key m)** , the binding of  **key** is added, removed or updated. If  **y** is  **None** , the binding is removed if it exists; otherwise, if  **y** is  **Some z** then  **key** is associated to  **z** in the resulting map.  If  **key** was already bound in  **m** to a value that is physically equal to  **z** ,  **m** is returned unchanged (the result of the function is then physically equal to  **m** ).

**Since** 4.06

*val singleton* :  **key -\> 'a -\> 'a t**

**singleton x y** returns the one-element map that contains a binding **y** for  **x** .

**Since** 3.12

*val remove* :  **key -\> 'a t -\> 'a t**

**remove x m** returns a map containing the same bindings as **m** , except for  **x** which is unbound in the returned map. If  **x** was not in  **m** ,  **m** is returned unchanged (the result of the function is then physically equal to  **m** ).

**Before4.03** Physical equality was not ensured.

*val merge* :  **(key -\> 'a option -\> 'b option -\> 'c option) -\>** **'a t -\> 'b t -\> 'c t**

**merge f m1 m2** computes a map whose keys are a subset of the keys of **m1** and of  **m2** . The presence of each such binding, and the corresponding value, is determined with the function  **f** . In terms of the  **find\_opt** operation, we have **find\_opt x (merge f m1 m2) = f x (find\_opt x m1) (find\_opt x m2)** for any key  **x** , provided that  **f x None None = None** .

**Since** 3.12

*val union* :  **(key -\> 'a -\> 'a -\> 'a option) -\>** **'a t -\> 'a t -\> 'a t**

**union f m1 m2** computes a map whose keys are a subset of the keys of  **m1** and of  **m2** .  When the same binding is defined in both arguments, the function  **f** is used to combine them. This is a special case of  **merge** :  **union f m1 m2** is equivalent to  **merge f' m1 m2** , where

\- **f' \_key None None = None**

\- **f' \_key (Some v) None = Some v**

\- **f' \_key None (Some v) = Some v**

\- **f' key (Some v1) (Some v2) = f key v1 v2**

**Since** 4.03

*val cardinal* :  **'a t -\> int**

Return the number of bindings of a map.

**Since** 3.12

### Bindings

*val bindings* :  **'a t -\> (key \* 'a) list**

Return the list of all bindings of the given map. The returned list is sorted in increasing order of keys with respect to the ordering  **Ord.compare** , where  **Ord** is the argument given to  **Map.Make** .

**Since** 3.12

*val min\_binding* :  **'a t -\> key \* 'a**

Return the binding with the smallest key in a given map (with respect to the  **Ord.compare** ordering), or raise **Not\_found** if the map is empty.

**Since** 3.12

*val min\_binding\_opt* :  **'a t -\> (key \* 'a) option**

Return the binding with the smallest key in the given map (with respect to the  **Ord.compare** ordering), or  **None** if the map is empty.

**Since** 4.05

*val max\_binding* :  **'a t -\> key \* 'a**

Same as  **Map.S.min\_binding** , but returns the binding with the largest key in the given map.

**Since** 3.12

*val max\_binding\_opt* :  **'a t -\> (key \* 'a) option**

Same as  **Map.S.min\_binding\_opt** , but returns the binding with the largest key in the given map.

**Since** 4.05

*val choose* :  **'a t -\> key \* 'a**

Return one binding of the given map, or raise  **Not\_found** if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

**Since** 3.12

*val choose\_opt* :  **'a t -\> (key \* 'a) option**

Return one binding of the given map, or  **None** if the map is empty. Which binding is chosen is unspecified, but equal bindings will be chosen for equal maps.

**Since** 4.05

### Searching

*val find* :  **key -\> 'a t -\> 'a**

**find x m** returns the current value of  **x** in  **m** , or raises  **Not\_found** if no binding for  **x** exists.

*val find\_opt* :  **key -\> 'a t -\> 'a option**

**find\_opt x m** returns  **Some v** if the current value of  **x** in  **m** is  **v** , or  **None** if no binding for  **x** exists.

**Since** 4.05

*val find\_first* :  **(key -\> bool) -\> 'a t -\> key \* 'a**

**find\_first f m** , where  **f** is a monotonically increasing function, returns the binding of  **m** with the lowest key  **k** such that  **f k** , or raises  **Not\_found** if no such key exists.

For example,  **find\_first (fun k -\> Ord.compare k x \>= 0) m** will return the first binding  **k, v** of  **m** where  **Ord.compare k x \>= 0** (intuitively:  **k \>= x** ), or raise  **Not\_found** if  **x** is greater than any element of  **m** .

**Since** 4.05

*val find\_first\_opt* :  **(key -\> bool) -\> 'a t -\> (key \* 'a) option**

**find\_first\_opt f m** , where  **f** is a monotonically increasing function, returns an option containing the binding of  **m** with the lowest key  **k** such that  **f k** , or  **None** if no such key exists.

**Since** 4.05

*val find\_last* :  **(key -\> bool) -\> 'a t -\> key \* 'a**

**find\_last f m** , where  **f** is a monotonically decreasing function, returns the binding of  **m** with the highest key  **k** such that  **f k** , or raises  **Not\_found** if no such key exists.

**Since** 4.05

*val find\_last\_opt* :  **(key -\> bool) -\> 'a t -\> (key \* 'a) option**

**find\_last\_opt f m** , where  **f** is a monotonically decreasing function, returns an option containing the binding of  **m** with the highest key  **k** such that  **f k** , or  **None** if no such key exists.

**Since** 4.05

### Traversing

*val iter* :  **(key -\> 'a -\> unit) -\> 'a t -\> unit**

**iter f m** applies  **f** to all bindings in map  **m** . **f** receives the key as first argument, and the associated value as second argument.  The bindings are passed to  **f** in increasing order with respect to the ordering over the type of the keys.

*val fold* :  **(key -\> 'a -\> 'acc -\> 'acc) -\> 'a t -\> 'acc -\> 'acc**

**fold f m init** computes  **(f kN dN ... (f k1 d1 init)...)** , where  **k1 ... kN** are the keys of all bindings in  **m** (in increasing order), and  **d1 ... dN** are the associated data.

### Transforming

*val map* :  **('a -\> 'b) -\> 'a t -\> 'b t**

**map f m** returns a map with same domain as  **m** , where the associated value  **a** of all bindings of  **m** has been replaced by the result of the application of  **f** to  **a** . The bindings are passed to  **f** in increasing order with respect to the ordering over the type of the keys.

*val mapi* :  **(key -\> 'a -\> 'b) -\> 'a t -\> 'b t**

Same as  **Map.S.map** , but the function receives as arguments both the key and the associated value for each binding of the map.

*val filter* :  **(key -\> 'a -\> bool) -\> 'a t -\> 'a t**

**filter f m** returns the map with all the bindings in  **m** that satisfy predicate  **f** . If every binding in  **m** satisfies  **f** , **m** is returned unchanged (the result of the function is then physically equal to  **m** )

**Before4.03** Physical equality was not ensured.

**Since** 3.12

*val filter\_map* :  **(key -\> 'a -\> 'b option) -\> 'a t -\> 'b t**

**filter\_map f m** applies the function  **f** to every binding of **m** , and builds a map from the results. For each binding **(k, v)** in the input map:

\-if  **f k v** is  **None** then  **k** is not in the result,

\-if  **f k v** is  **Some v'** then the binding  **(k, v')** is in the output map.

For example, the following function on maps whose values are lists

```
        filter_map
          (fun _k li -> match li with [] -> None | _::tl -> Some tl)
          m

```

drops all bindings of  **m** whose value is an empty list, and pops the first element of each value that is non-empty.

**Since** 4.11

*val partition* :  **(key -\> 'a -\> bool) -\> 'a t -\> 'a t \* 'a t**

**partition f m** returns a pair of maps  **(m1, m2)** , where **m1** contains all the bindings of  **m** that satisfy the predicate  **f** , and  **m2** is the map with all the bindings of **m** that do not satisfy  **f** .

**Since** 3.12

*val split* :  **key -\> 'a t -\> 'a t \* 'a option \* 'a t**

**split x m** returns a triple  **(l, data, r)** , where **l** is the map with all the bindings of  **m** whose key is strictly less than  **x** ; **r** is the map with all the bindings of  **m** whose key is strictly greater than  **x** ; **data** is  **None** if  **m** contains no binding for  **x** , or  **Some v** if  **m** binds  **v** to  **x** .

**Since** 3.12

### Predicates and comparisons

*val is\_empty* :  **'a t -\> bool**

Test whether a map is empty or not.

*val is\_singleton* :  **'a t -\> bool**

Test whether a map has exactly one element or not.

**Since** 5.5

*val mem* :  **key -\> 'a t -\> bool**

**mem x m** returns  **true** if  **m** contains a binding for  **x** , and  **false** otherwise.

*val equal* :  **('a -\> 'a -\> bool) -\> 'a t -\> 'a t -\> bool**

**equal cmp m1 m2** tests whether the maps  **m1** and  **m2** are equal, that is, contain equal keys and associate them with equal data.   **cmp** is the equality predicate used to compare the data associated with the keys.

*val compare* :  **('a -\> 'a -\> int) -\> 'a t -\> 'a t -\> int**

Total ordering between maps.  The first argument is a total ordering used to compare data associated with equal keys in the two maps.

*val for\_all* :  **(key -\> 'a -\> bool) -\> 'a t -\> bool**

**for\_all f m** checks if all the bindings of the map satisfy the predicate  **f** .

**Since** 3.12

*val exists* :  **(key -\> 'a -\> bool) -\> 'a t -\> bool**

**exists f m** checks if at least one binding of the map satisfies the predicate  **f** .

**Since** 3.12

### Converting

*val to\_list* :  **'a t -\> (key \* 'a) list**

**to\_list m** is  **Map.S.bindings** **m** .

**Since** 5.1

*val of\_list* :  **(key \* 'a) list -\> 'a t**

**of\_list bs** adds the bindings of  **bs** to the empty map, in list order (if a key is bound twice in  **bs** the last one takes over).

**Since** 5.1

*val to\_seq* :  **'a t -\> (key \* 'a) Seq.t**

Iterate on the whole map, in ascending order of keys

**Since** 4.07

*val to\_rev\_seq* :  **'a t -\> (key \* 'a) Seq.t**

Iterate on the whole map, in descending order of keys

**Since** 4.12

*val to\_seq\_from* :  **key -\> 'a t -\> (key \* 'a) Seq.t**

**to\_seq\_from k m** iterates on a subset of the bindings of  **m** , in ascending order of keys, from key  **k** or above.

**Since** 4.07

*val add\_seq* :  **(key \* 'a) Seq.t -\> 'a t -\> 'a t**

Add the given bindings to the map, in order.

**Since** 4.07

*val of\_seq* :  **(key \* 'a) Seq.t -\> 'a t**

Build a map from the given bindings

**Since** 4.07