1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="style.css" type="text/css">
<meta content="text/html; charset=iso-8859-1" http-equiv="Content-Type">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="Start" href="index.html">
<link rel="previous" href="Seq.html">
<link rel="next" href="Spacetime.html">
<link rel="Up" href="index.html">
<link title="Index of types" rel=Appendix href="index_types.html">
<link title="Index of extensions" rel=Appendix href="index_extensions.html">
<link title="Index of exceptions" rel=Appendix href="index_exceptions.html">
<link title="Index of values" rel=Appendix href="index_values.html">
<link title="Index of modules" rel=Appendix href="index_modules.html">
<link title="Index of module types" rel=Appendix href="index_module_types.html">
<link title="Arg" rel="Chapter" href="Arg.html">
<link title="Array" rel="Chapter" href="Array.html">
<link title="ArrayLabels" rel="Chapter" href="ArrayLabels.html">
<link title="Bigarray" rel="Chapter" href="Bigarray.html">
<link title="Bool" rel="Chapter" href="Bool.html">
<link title="Buffer" rel="Chapter" href="Buffer.html">
<link title="Bytes" rel="Chapter" href="Bytes.html">
<link title="BytesLabels" rel="Chapter" href="BytesLabels.html">
<link title="Callback" rel="Chapter" href="Callback.html">
<link title="CamlinternalFormat" rel="Chapter" href="CamlinternalFormat.html">
<link title="CamlinternalFormatBasics" rel="Chapter" href="CamlinternalFormatBasics.html">
<link title="CamlinternalLazy" rel="Chapter" href="CamlinternalLazy.html">
<link title="CamlinternalMod" rel="Chapter" href="CamlinternalMod.html">
<link title="CamlinternalOO" rel="Chapter" href="CamlinternalOO.html">
<link title="Char" rel="Chapter" href="Char.html">
<link title="Complex" rel="Chapter" href="Complex.html">
<link title="Condition" rel="Chapter" href="Condition.html">
<link title="Digest" rel="Chapter" href="Digest.html">
<link title="Dynlink" rel="Chapter" href="Dynlink.html">
<link title="Ephemeron" rel="Chapter" href="Ephemeron.html">
<link title="Event" rel="Chapter" href="Event.html">
<link title="Filename" rel="Chapter" href="Filename.html">
<link title="Float" rel="Chapter" href="Float.html">
<link title="Format" rel="Chapter" href="Format.html">
<link title="Fun" rel="Chapter" href="Fun.html">
<link title="Gc" rel="Chapter" href="Gc.html">
<link title="Genlex" rel="Chapter" href="Genlex.html">
<link title="Hashtbl" rel="Chapter" href="Hashtbl.html">
<link title="Int" rel="Chapter" href="Int.html">
<link title="Int32" rel="Chapter" href="Int32.html">
<link title="Int64" rel="Chapter" href="Int64.html">
<link title="Lazy" rel="Chapter" href="Lazy.html">
<link title="Lexing" rel="Chapter" href="Lexing.html">
<link title="List" rel="Chapter" href="List.html">
<link title="ListLabels" rel="Chapter" href="ListLabels.html">
<link title="Map" rel="Chapter" href="Map.html">
<link title="Marshal" rel="Chapter" href="Marshal.html">
<link title="MoreLabels" rel="Chapter" href="MoreLabels.html">
<link title="Mutex" rel="Chapter" href="Mutex.html">
<link title="Nativeint" rel="Chapter" href="Nativeint.html">
<link title="Obj" rel="Chapter" href="Obj.html">
<link title="Ocaml_operators" rel="Chapter" href="Ocaml_operators.html">
<link title="Oo" rel="Chapter" href="Oo.html">
<link title="Option" rel="Chapter" href="Option.html">
<link title="Parsing" rel="Chapter" href="Parsing.html">
<link title="Printexc" rel="Chapter" href="Printexc.html">
<link title="Printf" rel="Chapter" href="Printf.html">
<link title="Queue" rel="Chapter" href="Queue.html">
<link title="Random" rel="Chapter" href="Random.html">
<link title="Result" rel="Chapter" href="Result.html">
<link title="Scanf" rel="Chapter" href="Scanf.html">
<link title="Seq" rel="Chapter" href="Seq.html">
<link title="Set" rel="Chapter" href="Set.html">
<link title="Spacetime" rel="Chapter" href="Spacetime.html">
<link title="Stack" rel="Chapter" href="Stack.html">
<link title="StdLabels" rel="Chapter" href="StdLabels.html">
<link title="Stdlib" rel="Chapter" href="Stdlib.html">
<link title="Str" rel="Chapter" href="Str.html">
<link title="Stream" rel="Chapter" href="Stream.html">
<link title="String" rel="Chapter" href="String.html">
<link title="StringLabels" rel="Chapter" href="StringLabels.html">
<link title="Sys" rel="Chapter" href="Sys.html">
<link title="Thread" rel="Chapter" href="Thread.html">
<link title="ThreadUnix" rel="Chapter" href="ThreadUnix.html">
<link title="Uchar" rel="Chapter" href="Uchar.html">
<link title="Unit" rel="Chapter" href="Unit.html">
<link title="Unix" rel="Chapter" href="Unix.html">
<link title="UnixLabels" rel="Chapter" href="UnixLabels.html">
<link title="Weak" rel="Chapter" href="Weak.html"><title>Set</title>
</head>
<body>
<div class="navbar"><a class="pre" href="Seq.html" title="Seq">Previous</a>
<a class="up" href="index.html" title="Index">Up</a>
<a class="post" href="Spacetime.html" title="Spacetime">Next</a>
</div>
<h1>Module <a href="type_Set.html">Set</a></h1>
<pre><span id="MODULESet"><span class="keyword">module</span> Set</span>: <code class="code"><span class="keyword">sig</span></code> <a href="Set.html">..</a> <code class="code"><span class="keyword">end</span></code></pre><div class="info module top">
<div class="info-desc">
<p>Sets over ordered types.</p>
<p>This module implements the set data structure, given a total ordering
function over the set elements. All operations over sets
are purely applicative (no side-effects).
The implementation uses balanced binary trees, and is therefore
reasonably efficient: insertion and membership take time
logarithmic in the size of the set, for instance.</p>
<p>The <a href="Set.Make.html"><code class="code"><span class="constructor">Set</span>.<span class="constructor">Make</span></code></a> functor constructs implementations for any type, given a
<code class="code">compare</code> function.
For instance:</p>
<pre class="codepre"><code class="code"> <span class="keyword">module</span> <span class="constructor">IntPairs</span> =
<span class="keyword">struct</span>
<span class="keyword">type</span> t = int * int
<span class="keyword">let</span> compare (x0,y0) (x1,y1) =
<span class="keyword">match</span> <span class="constructor">Stdlib</span>.compare x0 x1 <span class="keyword">with</span>
0 <span class="keywordsign">-></span> <span class="constructor">Stdlib</span>.compare y0 y1
<span class="keywordsign">|</span> c <span class="keywordsign">-></span> c
<span class="keyword">end</span>
<span class="keyword">module</span> <span class="constructor">PairsSet</span> = <span class="constructor">Set</span>.<span class="constructor">Make</span>(<span class="constructor">IntPairs</span>)
<span class="keyword">let</span> m = <span class="constructor">PairsSet</span>.(empty |> add (2,3) |> add (5,7) |> add (11,13))
</code></pre>
<p>This creates a new module <code class="code"><span class="constructor">PairsSet</span></code>, with a new type <code class="code"><span class="constructor">PairsSet</span>.t</code>
of sets of <code class="code">int * int</code>.</p>
</div>
</div>
<hr width="100%">
<pre><span id="MODULETYPEOrderedType"><span class="keyword">module type</span> <a href="Set.OrderedType.html">OrderedType</a></span> = <code class="code"><span class="keyword">sig</span></code> <a href="Set.OrderedType.html">..</a> <code class="code"><span class="keyword">end</span></code></pre><div class="info">
<p>Input signature of the functor <a href="Set.Make.html"><code class="code"><span class="constructor">Set</span>.<span class="constructor">Make</span></code></a>.</p>
</div>
<pre><span id="MODULETYPES"><span class="keyword">module type</span> <a href="Set.S.html">S</a></span> = <code class="code"><span class="keyword">sig</span></code> <a href="Set.S.html">..</a> <code class="code"><span class="keyword">end</span></code></pre><div class="info">
<p>Output signature of the functor <a href="Set.Make.html"><code class="code"><span class="constructor">Set</span>.<span class="constructor">Make</span></code></a>.</p>
</div>
<pre><span id="MODULEMake"><span class="keyword">module</span> <a href="Set.Make.html">Make</a></span>: <div class="sig_block"><code class="code"><span class="keyword">functor</span> (</code><code class="code"><span class="constructor">Ord</span></code><code class="code"> : </code><code class="type"><a href="Set.OrderedType.html">OrderedType</a></code><code class="code">) <span class="keywordsign">-></span> </code><code class="type"><a href="Set.S.html">S</a></code><code class="type"> with type elt = Ord.t</code></div></pre><div class="info">
<p>Functor building an implementation of the set structure
given a totally ordered type.</p>
</div>
</body></html>
|
