+43
-1
lines changedFilter options
+43
-1
lines changed Original file line number Diff line number Diff line change
@@ -152,6 +152,19 @@ let print_with_scope ppf id = print ~with_scope:true ppf id
152 152 153 153
let print ppf id = print ~with_scope:false ppf id
154 154 155 +
(* For the documentation of ['a Ident.tbl], see ident.mli.
156 + 157 +
The implementation is a copy-paste specialization of
158 +
a balanced-tree implementation similar to Map.
159 +
['a tbl]
160 +
is a slightly more compact version of
161 +
[(Ident.t * 'a) list Map.Make(String)]
162 + 163 +
This implementation comes from Caml Light where duplication was
164 +
unavoidable in absence of functors. It works well enough, and so
165 +
far we have not had strong incentives to do the deduplication work
166 +
(implementation, tests, benchmarks, etc.).
167 +
*)
155 168
type 'a tbl =
156 169
Empty
157 170
| Node of 'a tbl * 'a data * 'a tbl * int
@@ -63,7 +63,36 @@ val highest_scope: int
63 63
val reinit: unit -> unit
64 64 65 65
type 'a tbl
66 -
(* Association tables from identifiers to type 'a. *)
66 +
(** ['a tbl] represents association tables from identifiers to values
67 +
of type ['a].
68 + 69 +
['a tbl] plays the role of map, but bindings can be looked up
70 +
from either the full Ident using [find_same], or just its
71 +
user-visible name using [find_name]. In general the two lookups may
72 +
not return the same result, as an identifier may have been shadowed
73 +
in the environment by a distinct identifier with the same name.
74 + 75 +
[find_all] returns the bindings for all idents of a given name,
76 +
most recently introduced first.
77 + 78 +
In other words,
79 +
['a tbl]
80 +
corresponds to
81 +
[(Ident.t * 'a) list Map.Make(String)]
82 +
and the implementation is very close to that representation.
83 + 84 +
Note in particular that searching among idents of the same name
85 +
takes linear time, and that [add] simply extends the list without
86 +
checking for duplicates. So it is not a good idea to implement
87 +
union by repeated [add] calls, which may result in many duplicated
88 +
identifiers and poor [find_same] performance. It is even possible
89 +
to build overly large same-name lists such that non-recursive
90 +
functions like [find_all] or [fold_all] blow the stack.
91 + 92 +
You should probably use [Map.Make(Ident)] instead, unless you
93 +
really need to query bindings by user-visible name, not just by
94 +
unique identifiers.
95 +
*)
67 96 68 97
val empty: 'a tbl
69 98
val add: t -> 'a -> 'a tbl -> 'a tbl
You can’t perform that action at this time.
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4