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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
|
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport"
content="width=device-width, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<meta name="author" content="韩暮秋">
<meta name="subtitle" content="暮秋小屋">
<meta name="description" content="这里是暮秋小屋,思念和灵感的寄存处">
<meta name="keywords" content="韩暮秋,MuqiuHan,'Muqiu Han', 'muqiu han', muqiuhan">
<title>Generalised signature | 暮秋小屋</title>
<link rel="icon" href="/favicon.ico">
<style>
@import url('https://fonts.googleapis.com/css2?family=Inter:wght@300;400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&family=Roboto+Mono&display=swap');
</style>
<!-- stylesheets list from _config.yml -->
<link rel="stylesheet" href="/css/style.css">
<!-- scripts list from _config.yml -->
<script src="/js/frame.js"></script>
<script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script>
<script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<meta name="generator" content="Hexo 6.3.0"></head>
<body>
<div class="mask-border">
</div>
<div class="wrapper">
<div class="header">
<div class="flex-container">
<div class="header-inner">
<div class="site-brand-container">
<a href="/">
暮秋小屋
</a>
</div>
<div id="menu-btn" class="menu-btn" onclick="toggleMenu()">
Menu
</div>
<nav class="site-nav">
<ul class="menu-list">
<li class="menu-item">
<a href="/">主页</a>
</li>
<li class="menu-item">
<a href="/categories/gallery/">日记本</a>
</li>
<li class="menu-item">
<a href="/tags/Medicine/">医学</a>
</li>
<li class="menu-item">
<a href="/tags/Technique/">计算机科学</a>
</li>
<li class="menu-item">
<a href="/tags/Life/">生活</a>
</li>
<li class="menu-item">
<a href="/about">关于</a>
</li>
<li class="menu-item search-btn">
<a href="#">Search</a>
</li>
</ul>
</nav>
</div>
</div>
</div>
<div class="main">
<div class="flex-container">
<article id="post">
<div class="post-head">
<div class="post-info">
<div class="tag-list">
<span class="post-tag">
<a href="/tags/Technique/">
Technique
</a>
</span>
<span class="post-tag">
<a href="/tags/Archive/">
Archive
</a>
</span>
<span class="post-tag">
<a href="/tags/OCaml/">
OCaml
</a>
</span>
</div>
<div class="post-title">
Generalised signature
</div>
<span class="post-date">
Oct 18, 2024
</span>
</div>
<div class="post-img">
<div class="h-line-primary"></div>
</div>
</div>
<div class="post-content">
<p>#ocaml #fp</p>
<blockquote>
<p><em>This post presents a technique for defining more reusable OCaml signatures, helping to maintain consistent APIs with minimal boilerplate. We’ll work through a few examples, which you can check out <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures">on GitHub</a>.</em></p>
</blockquote>
<h2 id="Indexable-containers"><a href="#Indexable-containers" class="headerlink" title="Indexable containers"></a>Indexable containers</h2><p>Consider the following definition of an <code>iter</code> function for some container type <code>t</code>:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> iter f t =</span><br><span class="line"> <span class="keyword">for</span> i = <span class="number">0</span> <span class="keyword">to</span> length t - <span class="number">1</span> <span class="keyword">do</span></span><br><span class="line"> f (get t i)</span><br><span class="line"> <span class="keyword">done</span></span><br></pre></td></tr></table></figure>
<p><code>iter</code> requires only that <code>t</code> comes with functions <code>get</code> and <code>length</code>. Many useful operations can be derived in terms of such indexing functions. To take advantage of this, let’s move <code>iter</code> into a functor and provide some other useful operations too:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> t</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> <span class="type">Foldable_of_indexable1</span> (<span class="type">I</span> : <span class="type">Indexable1</span>) : <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">open</span> <span class="type">I</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> iter : (<span class="symbol">'a</span> -> <span class="built_in">unit</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> iteri : (<span class="built_in">int</span> -> <span class="symbol">'a</span> -> <span class="built_in">unit</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> fold_left : (<span class="symbol">'acc</span> -> <span class="symbol">'a</span> -> <span class="symbol">'acc</span>) -> <span class="symbol">'acc</span> -> <span class="symbol">'a</span> t -> <span class="symbol">'acc</span></span><br><span class="line"> <span class="keyword">val</span> exists : (<span class="symbol">'a</span> -> <span class="built_in">bool</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> for_all : (<span class="symbol">'a</span> -> <span class="built_in">bool</span>) -> <span class="symbol">'a</span> t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> is_empty : _ t -> <span class="built_in">bool</span></span><br><span class="line"> <span class="comment">(* ... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<p>For many types, including <code>array</code>, the <code>get</code>-based definitions are identical to their hand-optimised equivalents (modulo functor application). We can imagine avoiding a lot of standard-library boilerplate – and potential for API inconsistency – by using many such functors <a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fn-1">1</a>. We’d end up defining exactly one <code>iter</code> function that suffices for all <code>Indexable</code> types.</p>
<p>All good so far. Now, let’s consider the <code>string</code> type.</p>
<p>A <code>string</code> is also an indexable container with <code>length</code> and <code>get</code> functions, albeit one that can only contain <code>char</code> values. It’s natural to expect to be able to re-use <code>Foldable_of_indexable1</code> in some way: indeed, our definition of <code>iter</code> above is exactly equal to the one in <code>Stdlib.String.iter</code>. Unfortunately, our <code>Indexable1</code> module type can only describe parametric containers:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> _ : (<span class="type">Indexable1</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="built_in">string</span>) = <span class="type">Stdlib</span>.<span class="type">String</span></span><br></pre></td></tr></table></figure>
<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">Error: Signature mismatch:</span><br><span class="line"> ...</span><br><span class="line"> Values do not match:</span><br><span class="line"> val get : t -> int -> char</span><br><span class="line"> is not included in</span><br><span class="line"> val get : t -> int -> 'a</span><br><span class="line"> File "string.mli", line 52, characters 0-57: Actual declaration</span><br></pre></td></tr></table></figure>
<p>We’re unable to tell the type system something like</p>
<blockquote>
<p><code>'a t = string</code> <em>implies</em> <code>'a = char</code></p>
</blockquote>
<p>as part of our substitution. This means that many types – including <code>string</code>, <code>bytes</code>, unboxed arrays and unboxed vectors – can’t benefit from our <code>Foldable_of_iterable1</code> definitions, even though their own definitions will be identical!</p>
<p>When we wrapped our code in the <code>Foldable_of_indexable1</code> functor, we needed to give it specific input and output module types, and the ones we picked artificially limited its usefulness. This is a hazard of functorising highly-generic code. As ever, we <em>could</em> solve the problem with copy-paste: a new <code>Indexable0</code> module type for non-parametric containers, and a new functor <code>Foldable_of_indexable0</code> with exactly the same implementations as our previous one.</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">(* Non-parametric indexable types *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable0</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> t</span><br><span class="line"> <span class="keyword">type</span> elt</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : t -> <span class="built_in">int</span> -> elt</span><br><span class="line"> <span class="keyword">val</span> length : t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">module</span> <span class="type">Foldable_of_indexable0</span> (<span class="type">I</span> : <span class="type">Indexable0</span>) : <span class="keyword">sig</span></span><br><span class="line"> <span class="comment">(* All with the same implementation as before... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<p>This definition suffers from the dual problem when we try to apply it to parameterised containers like <code>'a array</code>:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> _ : (<span class="type">Indexable0</span> <span class="keyword">with</span> <span class="keyword">type</span> t := <span class="symbol">'a</span> <span class="built_in">array</span>) = <span class="type">Stdlib</span>.<span class="type">Array</span></span><br></pre></td></tr></table></figure>
<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">Error: The type variable 'a is unbound in this type declaration.</span><br></pre></td></tr></table></figure>
<p>This time, we wanted to be able to say something like</p>
<blockquote>
<p><code>elt = 'a</code> <em>implies</em> <code>t = 'a array</code> (where <code>'a</code> is universally quantified),</p>
</blockquote>
<p>which is even more nonsensical than our previous attempt. Neither <code>Indexable0</code> nor <code>Indexable1</code> can be expressed in terms of the other. We need something more general.</p>
<h2 id="Something-more-general"><a href="#Something-more-general" class="headerlink" title="Something more general"></a>Something more general</h2><p>Interestingly, it’s possible to generalise <code>Indexable0</code> and <code>Indexable1</code> with <a target="_blank" rel="noopener" href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering">another layer of indirection</a> by making <code>elt</code> a type <em>operator</em>:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">IndexableN</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> t</span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">'a</span> elt</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span> elt</span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<p><code>elt</code> carries the type equalities needed for the <code>Indexable1</code> case, without forbidding the non-parametric implementation needed for the <code>Indexable0</code> case. Arrays can set <code>'a elt := 'a</code>, and strings can set <code>'a elt := char</code>. Indeed, we can do this in the general case:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">(** [Indexable0] is a special-case of [IndexableN] *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="type">Indexable0_to_N</span> = <span class="keyword">functor</span></span><br><span class="line"> (<span class="type">T</span> : <span class="type">Indexable0</span>) -></span><br><span class="line"> (<span class="type">T</span> : <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := elt)</span><br><span class="line"></span><br><span class="line"><span class="comment">(** [Indexable1] is a special-case of [IndexableN] *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="type">Indexable1_to_N</span> = <span class="keyword">functor</span></span><br><span class="line"> (<span class="type">T</span> : <span class="type">Indexable1</span>) -></span><br><span class="line"> (<span class="type">T</span> : <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> t := <span class="symbol">'a</span> <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := <span class="symbol">'a</span>)</span><br></pre></td></tr></table></figure>
<p>Now we can define a single <code>Foldable_of_indexableN</code> functor (with exactly the same implementations as before), and it will work for polymorphic and monomorphic containers. Neat!</p>
<p><img src="https://www.craigfe.io/posts/generalised-signatures/dag-indexable.png" alt="A lattice showing Indexable0 and Indexable1 being generalised by IndexableN."></p>
<p>In the general case, when you notice that different signatures are sharing common functions, it’s often possible to unify them under a common interface with the following two steps:</p>
<ol>
<li><p><em><strong>generalise</strong></em>. Convert pure type variables into type operators (as in <code>'a</code> → <code>'a elt</code>), to support use-cases like instantiating those variables to fixed types. Add type parameters to existing types to carry type equalities between them (as in <code>'a t</code> / <code>'a elt</code>), to support use-cases where these types depend on each other.</p>
</li>
<li><p><em><strong>specialise</strong></em>. Use destructive substitution (<code>:=</code>) to eliminate those types and type parameters when they’re not needed. We’re taking advantage of the <a target="_blank" rel="noopener" href="https://github.com/ocaml/ocaml/pull/792">more powerful destructive substitution</a> offered by OCaml 4.06, which allows us to freely undo our generalisation step.</p>
</li>
</ol>
<p>The truly magical part of this trick is that – with better support for destructive type substitutions recently added to Odoc – it can be made <strong>completely invisible</strong><a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fn-2">2</a> in documentation!</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">type</span> _ t</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">'a</span> t -> <span class="built_in">int</span> -> <span class="symbol">'a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -> <span class="built_in">int</span></span><br><span class="line"><span class="keyword">end</span></span><br><span class="line"></span><br><span class="line"><span class="comment">(** This module gets identical documentation to the one above! *)</span></span><br><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Indexable1'</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">include</span> <span class="type">IndexableN</span> <span class="keyword">with</span> <span class="keyword">type</span> <span class="symbol">'a</span> elt := <span class="symbol">'a</span> <span class="comment">(** @inline *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<h2 id="What’s-the-cost"><a href="#What’s-the-cost" class="headerlink" title="What’s the cost?"></a>What’s the cost?</h2><p>One unavoidable limitation is in what sort of operations we can put in the <code>Foldable_of_indexable</code> functor. Suppose our initial attempt at generalising containers included a <code>sum</code> function:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">let</span> sum : <span class="built_in">int</span> t -> t = fold_left ( + ) <span class="number">0</span></span><br></pre></td></tr></table></figure>
<p><code>sum</code> requires a container that can hold <code>int</code> values, which is clearly not possible for strings as the type system will happily tell us:</p>
<figure class="highlight text"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"> | let sum = fold_left ( + ) 0</span><br><span class="line"> ^^^^^</span><br><span class="line">Error: This expression has type int -> int -> int</span><br><span class="line"> but an expression was expected of type int -> 'a elt -> int</span><br><span class="line"> Type int is not compatible with type 'a elt</span><br></pre></td></tr></table></figure>
<p>To state the obvious, we can’t rely on parametricity in our container functions if we want them to work on non-parametric containers. The natural solution here would be to define such parametric-only functions in a separate functor.</p>
<h2 id="Other-examples"><a href="#Other-examples" class="headerlink" title="Other examples"></a>Other examples</h2><p>Indexable containers aren’t the only example of generalised signatures in the real world. Indeed, many other data-structures and design patterns have APIs that can be unified in this way. Consider the case of <em>hashtables</em>, which have a huge space of possible implementations:</p>
<ul>
<li><p><code>key</code> types can be left polymorphic by using a magic hash function like <code>caml_hash</code> (as in <a target="_blank" rel="noopener" href="https://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.html"><code>Stdlib.Hashtbl</code></a>), or fixed by a user-specified hash function (as in <a target="_blank" rel="noopener" href="https://caml.inria.fr/pub/docs/manual-ocaml/libref/Hashtbl.Make.html"><code>Stdlib.Hashtbl.Make</code></a>).</p>
</li>
<li><p><code>value</code> types can be left polymorphic, fixed by the user (as in persistent hashtables like <a target="_blank" rel="noopener" href="https://mirage.github.io/index/index/Index/Make/index.html"><code>Index</code></a>), or even determined by the keys used to index them (as in universal maps like <a target="_blank" rel="noopener" href="https://erratique.ch/software/hmap/doc/Hmap"><code>Hmap</code></a>).</p>
</li>
</ul>
<p>Initially, it looks like these different hashtables will each require their own hand-written signature (and this is what the standard library does with its hashtables). However, with enough type parameters, these different implementations can all be unified under a single <code>Hashtbl_generalised</code> module type:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Hashtbl_generalised</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="comment">(** We have three types ([t], [key] and [value]) and three type variables:</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> - ['k]/['v] allow the hashtable to determine key/value types;</span></span><br><span class="line"><span class="comment"> - ['a] is carried from keys to corresponding values, allowing the key to</span></span><br><span class="line"><span class="comment"> determine the types of values. *)</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> create : <span class="built_in">int</span> -> (_, _) t</span><br><span class="line"> <span class="keyword">val</span> replace : (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t -> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key -> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span> -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> remove : (<span class="symbol">'k</span>, _) t -> (<span class="symbol">'k</span>, _) key -> <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> find_opt : (<span class="symbol">'k</span>, <span class="symbol">'v</span>) t -> (<span class="symbol">'k</span>, <span class="symbol">'a</span>) key -> (<span class="symbol">'v</span>, <span class="symbol">'a</span>) <span class="keyword">value</span> option</span><br><span class="line"> <span class="comment">(* ... *)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<p>We can then implement our different hashtable signatures as specialisations:</p>
<p><img src="https://www.craigfe.io/posts/generalised-signatures/dag-hashtables.png" alt="A lattice showing four different `Hashtbl` module types being generalised by `Hashtbl_generalised`."></p>
<p>For instance, for the regular polymorphic hashtable:</p>
<figure class="highlight ocaml"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">module</span> <span class="keyword">type</span> <span class="type">Poly_hash</span> = <span class="keyword">sig</span></span><br><span class="line"> <span class="keyword">include</span> <span class="type">Hashtbl_generalised</span></span><br><span class="line"> <span class="keyword">with</span> <span class="keyword">type</span> (<span class="symbol">'k</span>, _) key := <span class="symbol">'k</span></span><br><span class="line"> <span class="keyword">and</span> <span class="keyword">type</span> (<span class="symbol">'v</span>, _) <span class="keyword">value</span> := <span class="symbol">'v</span> <span class="comment">(** @inline **)</span></span><br><span class="line"><span class="keyword">end</span></span><br></pre></td></tr></table></figure>
<p>The other specialisations are very similar (see <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures/blob/main/examples/hashtbl.ml">here</a> for the specifics).</p>
<p>What is it that makes <code>Hashtable_generalised</code> a good parent interface for these four flavours of hashtable? To get some insight, we can notice that each of the type parameters (<code>'k</code>, <code>'v</code>, and <code>'a</code>) connects its own pair of types:</p>
<p><code>hashtbl_generalised</code></p>
<p><img src="https://www.craigfe.io/posts/generalised-signatures/dep-hashtbl_generalised.png"></p>
<p>Framed this way, the type parameter <code>'k</code> exists solely to carry type information between hashtables and their keys (using a type equality at call sites). Similarly, <code>'v</code> bridges between hashtables and values, and <code>'a</code> between keys and values. From here, each of our hashtable variants uses destructive subsitution (<code>:=</code>) to prune away unnecessary bridges and express some sort of dependency relation between the types:</p>
<table>
<thead>
<tr>
<th></th>
<th></th>
</tr>
</thead>
<tbody><tr>
<td><code>poly_hash</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-poly_hash.png"><br><br>Keys and value types constrain <code>t</code> at call-sites.</td>
<td><code>mono_hash</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-mono_hash.png"><br><br>The value type constrains <code>t</code>, but <code>key</code>is fixed by a functor.</td>
</tr>
<tr>
<td><code>persistent</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-persistent.png"><br><br>Both key and value types are fixed by a functor.</td>
<td><code>universal</code><br><br><img src="https://www.craigfe.io/posts/generalised-signatures/dep-universal.png"><br><br>Each key’s type constrains the corresponding value’s type.</td>
</tr>
</tbody></table>
<p>In this case, it’s not feasible for all these data structures to share the same implementation, but it’s still valuable for them to implement a common core API: it ensures consistency of the user-facing functions, allows sharing of documentation, and may even allow these implementations to share a common test suite.</p>
<h2 id="Conclusion"><a href="#Conclusion" class="headerlink" title="Conclusion"></a>Conclusion</h2><p>The full code for our <code>Indexable</code> and <code>Hashtbl</code> examples, including explicit definitions of each of the module types, can be found in the <a target="_blank" rel="noopener" href="https://github.(com/CraigFe/generalised-signatures)"><code>generalised-signatures</code> repository</a>. This repository also contains and a <a target="_blank" rel="noopener" href="https://github.com/CraigFe/generalised-signatures/blob/main/examples/monads.ml">third demonstration</a> of this technique being used to express monad-like signatures. The auto-generated documentation for these examples can be <a target="_blank" rel="noopener" href="https://craigfe.github.io/generalised-signatures/generalised_signatures/Generalised_signatures/index.html">viewed online</a>.x</p>
<p>Thanks for making it to the end; I hope you picked up something useful. If you think it would help others in your network, I’d appreciate it if you <a target="_blank" rel="noopener" href="https://twitter.com/share?url=NaN&text=%E2%80%9CGeneralised%20signatures%E2%80%9D,%20a%20post%20by%20Craig%20Ferguson.%20&via=_craigfe">shared it</a> with them.</p>
<hr>
<h4 id="Appendix-A-Haskell-suffers-too"><a href="#Appendix-A-Haskell-suffers-too" class="headerlink" title="Appendix A: Haskell suffers too"></a>Appendix A: Haskell suffers too</h4><p>The typeclasses in Haskell’s <a target="_blank" rel="noopener" href="https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Foldable.html">base</a> have the same “polymorphic-instances-only” property as our <code>Indexable1</code> signature (unsurprising, since it doesn’t provide any unboxed container types).</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="type">Indexable1</span> f <span class="keyword">where</span></span> <span class="comment">-- Polymorphic instances only</span></span><br><span class="line"> get :: f a -> <span class="type">Int</span> -> a</span><br><span class="line"> length :: f a -> <span class="type">Int</span></span><br></pre></td></tr></table></figure>
<p>A similar trick can be performed there to generalise the typeclass instances for monomorphic containers like <code>Text</code>:</p>
<figure class="highlight haskell"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">{-# LANGUAGE TypeFamilies #-}</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">type</span> <span class="keyword">family</span> <span class="type">Elt</span> container <span class="comment">-- Relate containers to their element type</span></span></span><br><span class="line"><span class="class"><span class="keyword">type</span> instance <span class="type">Elt</span> [a] = a</span></span><br><span class="line"><span class="class"><span class="keyword">type</span> instance <span class="type">Elt</span> <span class="type">Text</span> = <span class="type">Char</span></span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="type">IndexableN</span> c <span class="keyword">where</span></span></span><br><span class="line"> get :: c -> <span class="type">Int</span> -> <span class="type">Elt</span> c</span><br><span class="line"> length :: c -> <span class="type">Int</span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">IndexableN</span> [a] <span class="keyword">where</span></span> <span class="comment">-- Polymorphic instance</span></span><br><span class="line"> get = (!!)</span><br><span class="line"> length = <span class="type">Prelude</span>.length</span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class"><span class="keyword">instance</span> <span class="type">IndexableN</span> <span class="type">Text</span> <span class="keyword">where</span></span> <span class="comment">-- Monomorphic instance</span></span><br><span class="line"> get = <span class="type">Text</span>.index</span><br><span class="line"> length = <span class="type">Text</span>.length</span><br></pre></td></tr></table></figure>
<p>As in the OCaml version, we use an <code>Elt</code> type operator to carry the equality needed for the monomorphic case. This time we used type families to specify the relations explicitly, but we could have used multi-parameter type classes for something more akin to the OCaml functor implementation. See the <a target="_blank" rel="noopener" href="https://hackage.haskell.org/package/mono-traversable">mono-traversable</a> package for more of this sort of trickery in Haskell.</p>
<hr>
<ol>
<li>This is the approach taken by Jane Street’s <a target="_blank" rel="noopener" href="https://github.com/janestreet/base">base</a>, and is very similar to the Haskell notion of building standard libraries from type-class instances.<a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fnref-1">↩</a></li>
<li>This example uses the <code>(** @inline *)</code> tag to ensure that Odoc doesn’t leak that <code>Indexable1'</code> is implemented in terms of <code>IndexableN</code>.<a target="_blank" rel="noopener" href="https://www.craigfe.io/posts/generalised-signatures#fnref-2">↩</a></li>
</ol>
</div>
<script>
window.onload = detectors();
</script>
<div class="post-footer">
<div class="h-line-primary"></div>
<nav class="post-nav">
<div class="prev-item">
</div>
<div class="next-item">
<div class="icon arrow-right"></div>
<div class="post-link">
<a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/">Next</a>
</div>
</div>
</nav>
</div>
<div class="post-comment">
</div>
</article>
</div>
</div>
<div class="footer">
<div class="flex-container">
<div class="footer-text">
|
希望路过的人可以添点柴火让这里暖和点
</div>
</div>
</div>
</div>
<div class="search-popup">
<div class="search-popup-overlay">
</div>
<div class="search-popup-window" >
<div class="search-header">
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="Search Anything" spellcheck="false"
type="search" class="search-input">
</div>
<div class="search-close-btn">
<div class="icon close-btn"></div>
</div>
</div>
<div class="search-result-container">
</div>
</div>
</div>
<script>
const searchConfig = {
path : "/search.xml",
top_n_per_article: "1",
unescape : "false",
trigger: "auto",
preload: "false"
}
</script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/search.js"></script>
<script src="/js/search.js"></script>
</body>
</html>
|