diff options
| author | muqiuhan <[email protected]> | 2024-10-18 15:52:48 +0000 |
|---|---|---|
| committer | muqiuhan <[email protected]> | 2024-10-18 15:52:48 +0000 |
| commit | 3f213808be92656a03f60bd23b5652857afa8640 (patch) | |
| tree | dd7bd78e65fd2480ab741a2f08a4095be99f045f /2024/10/18/Generalised-signature/index.html | |
| parent | 21ead6027c75cca30c0649b6fd0b0bbfbfb12c5c (diff) | |
| download | blog-3f213808be92656a03f60bd23b5652857afa8640.tar.gz | |
deploy: 726514ed15d170ba23ee3149104de5bee06cdf20
Diffstat (limited to '2024/10/18/Generalised-signature/index.html')
| -rw-r--r-- | 2024/10/18/Generalised-signature/index.html | 383 |
1 files changed, 0 insertions, 383 deletions
diff --git a/2024/10/18/Generalised-signature/index.html b/2024/10/18/Generalised-signature/index.html deleted file mode 100644 index b5297985..00000000 --- a/2024/10/18/Generalised-signature/index.html +++ /dev/null @@ -1,383 +0,0 @@ -<!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> |
