summaryrefslogtreecommitdiff
path: root/2024/10/18/Generalised-signature/index.html
diff options
context:
space:
mode:
authormuqiuhan <[email protected]>2024-10-18 15:45:18 +0000
committermuqiuhan <[email protected]>2024-10-18 15:45:18 +0000
commit3c03c9b03a084984383b510f6b795df3bfaf5ca7 (patch)
tree7daa9d22c80f8240066a0754c7716b2c38a2f1b2 /2024/10/18/Generalised-signature/index.html
parent4b590d57084adcd99c7b73b4485282bbb8455d01 (diff)
downloadblog-3c03c9b03a084984383b510f6b795df3bfaf5ca7.tar.gz
deploy: e8ad1ffc5e1b38c1ac5bb25141187398e15d1236
Diffstat (limited to '2024/10/18/Generalised-signature/index.html')
-rw-r--r--2024/10/18/Generalised-signature/index.html383
1 files changed, 383 insertions, 0 deletions
diff --git a/2024/10/18/Generalised-signature/index.html b/2024/10/18/Generalised-signature/index.html
new file mode 100644
index 00000000..b5297985
--- /dev/null
+++ b/2024/10/18/Generalised-signature/index.html
@@ -0,0 +1,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">&#x27;a</span> t</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">int</span> -&gt; <span class="symbol">&#x27;a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -&gt; <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">&#x27;a</span> -&gt; <span class="built_in">unit</span>) -&gt; <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> iteri : (<span class="built_in">int</span> -&gt; <span class="symbol">&#x27;a</span> -&gt; <span class="built_in">unit</span>) -&gt; <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> fold_left : (<span class="symbol">&#x27;acc</span> -&gt; <span class="symbol">&#x27;a</span> -&gt; <span class="symbol">&#x27;acc</span>) -&gt; <span class="symbol">&#x27;acc</span> -&gt; <span class="symbol">&#x27;a</span> t -&gt; <span class="symbol">&#x27;acc</span></span><br><span class="line"> <span class="keyword">val</span> exists : (<span class="symbol">&#x27;a</span> -&gt; <span class="built_in">bool</span>) -&gt; <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> for_all : (<span class="symbol">&#x27;a</span> -&gt; <span class="built_in">bool</span>) -&gt; <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">bool</span></span><br><span class="line"> <span class="keyword">val</span> is_empty : _ t -&gt; <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">&#x27;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 -&gt; int -&gt; char</span><br><span class="line"> is not included in</span><br><span class="line"> val get : t -&gt; int -&gt; &#x27;a</span><br><span class="line"> File &quot;string.mli&quot;, 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>&#39;a t = string</code>    <em>implies</em>    <code>&#39;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 -&gt; <span class="built_in">int</span> -&gt; elt</span><br><span class="line"> <span class="keyword">val</span> length : t -&gt; <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>&#39;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">&#x27;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 &#x27;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 = &#39;a</code>    <em>implies</em>    <code>t = &#39;a array</code>    (where <code>&#39;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">&#x27;a</span> t</span><br><span class="line"> <span class="keyword">type</span> <span class="symbol">&#x27;a</span> elt</span><br><span class="line"></span><br><span class="line"> <span class="keyword">val</span> get : <span class="symbol">&#x27;a</span> t -&gt; <span class="built_in">int</span> -&gt; <span class="symbol">&#x27;a</span> elt</span><br><span class="line"> <span class="keyword">val</span> length : _ t -&gt; <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>&#39;a elt := &#39;a</code>, and strings can set <code>&#39;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>) -&gt;</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">&#x27;a</span> t := <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">&#x27;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>) -&gt;</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">&#x27;a</span> t := <span class="symbol">&#x27;a</span> <span class="type">T</span>.t <span class="keyword">and</span> <span class="keyword">type</span> <span class="symbol">&#x27;a</span> elt := <span class="symbol">&#x27;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>&#39;a</code> → <code>&#39;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>&#39;a t</code> &#x2F; <code>&#39;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">&#x27;a</span> t -&gt; <span class="built_in">int</span> -&gt; <span class="symbol">&#x27;a</span></span><br><span class="line"> <span class="keyword">val</span> length : _ t -&gt; <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&#x27;</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">&#x27;a</span> elt := <span class="symbol">&#x27;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 -&gt; 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 -&gt; int -&gt; int</span><br><span class="line"> but an expression was expected of type int -&gt; &#x27;a elt -&gt; int</span><br><span class="line"> Type int is not compatible with type &#x27;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"> - [&#x27;k]/[&#x27;v] allow the hashtable to determine key/value types;</span></span><br><span class="line"><span class="comment"> - [&#x27;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">&#x27;k</span>, <span class="symbol">&#x27;v</span>) t</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">&#x27;k</span>, <span class="symbol">&#x27;a</span>) key</span><br><span class="line"> <span class="keyword">type</span> (<span class="symbol">&#x27;v</span>, <span class="symbol">&#x27;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> -&gt; (_, _) t</span><br><span class="line"> <span class="keyword">val</span> replace : (<span class="symbol">&#x27;k</span>, <span class="symbol">&#x27;v</span>) t -&gt; (<span class="symbol">&#x27;k</span>, <span class="symbol">&#x27;a</span>) key -&gt; (<span class="symbol">&#x27;v</span>, <span class="symbol">&#x27;a</span>) <span class="keyword">value</span> -&gt; <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> remove : (<span class="symbol">&#x27;k</span>, _) t -&gt; (<span class="symbol">&#x27;k</span>, _) key -&gt; <span class="built_in">unit</span></span><br><span class="line"> <span class="keyword">val</span> find_opt : (<span class="symbol">&#x27;k</span>, <span class="symbol">&#x27;v</span>) t -&gt; (<span class="symbol">&#x27;k</span>, <span class="symbol">&#x27;a</span>) key -&gt; (<span class="symbol">&#x27;v</span>, <span class="symbol">&#x27;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">&#x27;k</span>, _) key := <span class="symbol">&#x27;k</span></span><br><span class="line"> <span class="keyword">and</span> <span class="keyword">type</span> (<span class="symbol">&#x27;v</span>, _) <span class="keyword">value</span> := <span class="symbol">&#x27;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>&#39;k</code>, <code>&#39;v</code>, and <code>&#39;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>&#39;k</code> exists solely to carry type information between hashtables and their keys (using a type equality at call sites). Similarly, <code>&#39;v</code> bridges between hashtables and values, and <code>&#39;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 -&gt; <span class="type">Int</span> -&gt; a</span><br><span class="line"> length :: f a -&gt; <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">&#123;-# LANGUAGE TypeFamilies #-&#125;</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 -&gt; <span class="type">Int</span> -&gt; <span class="type">Elt</span> c</span><br><span class="line"> length :: c -&gt; <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&#39;</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>