Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 172 lines (129 sloc) 4.771 kb
991ccf1 @VictorNicollet Initial import of Ohm
authored
1 (** Collapsing immutable values.
2
3 Immutable data structures allow the reuse of common sub-expression between
4 complex values: two lists that have the same tail may indeed share the same
5 tail value, two binary trees may share certain sub-trees, and so on. In
6 practice, such sharing only happens when the second value was constructed
7 from the first. If two independent values happen to share most of their
8 content, there will be no actual memory sharing. This creates an
9 unnecessary memory load, because more memory is used than otherwise necessary.
10
11 Should this increased memory usage become an issue (for instance, for
12 long-lived values in a web server), collapsing common sub-expressions
13 eliminates repetition by recursively traversing the objects and ensuring for
14 every two sub-expression [e] and [e'] that if [e = e'] then [e == e'].
15
16 This module provides basic primitives for constructing a collapser for a
17 specific type.
18
19 @author Victor Nicollet
20 @version 1.0
21 *)
22
23
24 (** A collapser function. Such a function guarantees that if [e] and [e'] are
25 equal, then [f e == f e']. The actual meaning of {i are equal} is to be
26 determined by the user: it can be standard equality ([e = e']), referential
27 equality ([e == e']), comparison equality ([compare e e' = 0]) or any
28 other possible definition.
29 *)
30 type 'a t = 'a -> 'a
31
32 (** A referential equality collapser. Returns its argument untouched,
33 which ensures that [keep e == keep e'] if [e == e']. Use this compressor
34 when working with otherwise non-comparable values (functions, objects).
35
36 {[
37 let a = "hello", (fun a -> a) in
38 let b = "hello", (fun a -> a + 1) in
39
40 let collapse = Compressor.pair (Compressor.basic ()) (Compressor.keep) in
41
42 let a = collapse a in
43 let b = collapse b in
44
45 fst a == fst b (* true *)
46 ]}
47 *)
48 val keep : 'a t
49
50 (** A list collapser. Uses an item collapser to collapse the list items,
51 then collapses the list tail itself.
52
53 {[
54 let x = ["a";"b";"c"]
55 let y = ["b";"c"]
56
57 let collapse = Compressor.list (Compressor.basic ()) in
58
59 let x = collapse x in
60 let y = collapse y in
61
62 List.tl x == y (* true *)
63 ]}
64
65 *)
66 val list : 'a t -> 'a list t
67
68 (** An option collapser. Applies the provided collapser to the
69 value, if present.
70 *)
71 val option : 'a t -> 'a option t
72
73 (** A basic type collapser. [basic ()] is a collapser that works based on
74 equality, so that [f e == f e'] if [e = e']. It is intended for [float] and
75 [string] types, as [int] and [bool] values gain nothing from being collapsed.
76
77 Do not use this collapser for values that have sub-values you wish to collapse,
78 because it will not recurse.
79
80 {[
81 let a = "hello" in
82 let b = "hello" in
83
84 let string = Compressor.basic () in
85
86 let a = string a in
87 let b = string b in
88
89 a == b (* true *)
90 ]}
91 *)
92 val basic : unit -> 'a t
93
94 (** A pair compressor. Recursively compresses the two pair elements.
95
96 {[
97 let a = "hello", `EQUAL in
98 let b = "hello", `EQUAL in
99
100 let collapse = Compressor.pair (Compressor.basic (), Compressor.keep)
101
102 let a = collapse a in
103 let b = collapse b in
104
105 a == b (* true *)
106 ]}
107 *)
108 val pair : 'a t -> 'b t -> ('a * 'b) t
109
110 (** A simple value collapser. [let f = simple recurse] uses equality, so
111 that [f e == f e'] if [e = e']. The argument [recurse] is a function
112 which recursively compresses the contents of the argument, and will
113 be called if no equal value has been encountered yet.
114
115 Use this function whenever a recursive value must be handled.
116
117 {[
118 type t = { a : string ; b : string }
119
120 let x = { a = "hello" ; b = "hello" }
121 let y = { a = "hello" ; b = "hello" }
122
123 let string = Compressor.basic ()
124 let collapse = Compressor.simple
125 (fun x -> { a = string x.a ; b = string x.b })
126
127 let x = collapse x
128 let y = collapse y
129
130 x == y (* true *)
131 x.a == x.b (* true *)
132 ]}
133 *)
134 val simple : ('a -> 'a) -> 'a t
135
136 (** An arbitrary value collapser. [let f = simple project recurse] uses
137 the [project] function to determine equality, so that [f e == f e']
138 if [project e = project e']. This is used to turn non-comparable
139 objects into comparable objects. [recurse] is expected to collapse
140 sub-values of the argument, and will be called if no equal value
141 has been encountered yet.
142
143 {[
144 let x = object
145 method a = "hello"
146 method b = "hello"
147 end
148
149 let y = object
150 method a = "hello"
151 method b = "hello"
152 end
153
154 let string = Compressor.basic ()
155 let collapse = Compressor.any
156 (fun x -> x # a, x # b)
157 (fun x -> (object
158 val a = string (x # a)
159 method a = a
160 val b = string (x # b)
161 method b = b
162 end))
163
164 let x = collapse x in
165 let y = collapse y in
166
167 x == y (* true *)
168 x # a == x # b (* true *)
169 ]}
170 *)
171 val any : ('a -> 'b) -> ('a -> 'a) -> 'a t
Something went wrong with that request. Please try again.