diff options
27 files changed, 434 insertions, 938 deletions
diff --git a/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html b/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html index efff6f07..3134bfc8 100644 --- a/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html +++ b/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/index.html @@ -338,11 +338,6 @@ <nav class="post-nav"> <div class="prev-item"> - <div class="icon arrow-left"></div> - <div class="post-link"> - <a href="/2024/10/18/Generalised-signature/">Prev</a> - </div> - </div> <div class="next-item"> 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> diff --git a/archives/2024/10/index.html b/archives/2024/10/index.html index 5e05f9d0..0e738df5 100644 --- a/archives/2024/10/index.html +++ b/archives/2024/10/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/"> 10 Tips for Productive FSharp Scripting diff --git a/archives/2024/index.html b/archives/2024/index.html index 99ae642d..ad6c7f28 100644 --- a/archives/2024/index.html +++ b/archives/2024/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/"> 10 Tips for Productive FSharp Scripting @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/09/08/%E4%B8%AD%E8%80%81%E5%B9%B4%E4%BA%BA%E6%B2%89%E8%BF%B7%E6%89%8B%E6%9C%BA%E7%9A%84%E9%97%AE%E9%A2%98/"> + + 中老年人沉迷手机的问题 + + </a> + </div> + + <span class="post-date">Sep 8, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/2024/page/2/index.html b/archives/2024/page/2/index.html index 6bdae82d..4f48af01 100644 --- a/archives/2024/page/2/index.html +++ b/archives/2024/page/2/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/09/08/%E4%B8%AD%E8%80%81%E5%B9%B4%E4%BA%BA%E6%B2%89%E8%BF%B7%E6%89%8B%E6%9C%BA%E7%9A%84%E9%97%AE%E9%A2%98/"> - - 中老年人沉迷手机的问题 - - </a> - </div> - - <span class="post-date">Sep 8, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/09/07/%E7%BB%99%E5%AD%A9%E5%AD%90%E4%BB%AC%E7%9A%84%E8%AF%9D/"> 什么玩意儿都是 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/06/27/OCaml-News-2024-5/"> + + OCaml News 2024-5 + + </a> + </div> + + <span class="post-date">Jun 27, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/2024/page/3/index.html b/archives/2024/page/3/index.html index ba3788bf..c0868cc8 100644 --- a/archives/2024/page/3/index.html +++ b/archives/2024/page/3/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/06/27/OCaml-News-2024-5/"> - - OCaml News 2024-5 - - </a> - </div> - - <span class="post-date">Jun 27, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/06/06/NET-AOT-%E4%B8%8B%E7%9A%84-F-%E5%91%BD%E4%BB%A4%E8%A1%8C%E5%8F%82%E6%95%B0%E8%A7%A3%E6%9E%90%E5%BA%93%E9%80%89%E6%8B%A9/"> .NET AOT 下的 F# 命令行参数解析库选择 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/02/26/OCaml-News-2024-3/"> + + OCaml News 2024-3 + + </a> + </div> + + <span class="post-date">Feb 26, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/2024/page/4/index.html b/archives/2024/page/4/index.html index fe846df6..4cc7624b 100644 --- a/archives/2024/page/4/index.html +++ b/archives/2024/page/4/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/02/26/OCaml-News-2024-3/"> - - OCaml News 2024-3 - - </a> - </div> - - <span class="post-date">Feb 26, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/02/07/%E4%BA%8C%E3%80%87%E4%BA%8C%E5%9B%9B%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%B8%83%E6%97%A5/"> 二〇二四年二月七日 diff --git a/archives/index.html b/archives/index.html index fbff07d6..840e176b 100644 --- a/archives/index.html +++ b/archives/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/"> 10 Tips for Productive FSharp Scripting @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/09/08/%E4%B8%AD%E8%80%81%E5%B9%B4%E4%BA%BA%E6%B2%89%E8%BF%B7%E6%89%8B%E6%9C%BA%E7%9A%84%E9%97%AE%E9%A2%98/"> + + 中老年人沉迷手机的问题 + + </a> + </div> + + <span class="post-date">Sep 8, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/10/index.html b/archives/page/10/index.html index 9cb753a8..ff83c78a 100644 --- a/archives/page/10/index.html +++ b/archives/page/10/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/02/02/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%BA%8C%E6%97%A5/"> - - 二零二三年二月二日 - - </a> - </div> - - <span class="post-date">Feb 2, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/02/01/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%B8%80%E6%97%A5/"> 二零二三年二月一日 @@ -319,6 +301,26 @@ </div> + + + + + <div class="year-title">2021</div> + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2021/03/27/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%80%E5%B9%B4%E4%B8%89%E6%9C%88%E4%BA%8C%E5%8D%81%E4%B8%83%E6%97%A5/"> + + 二零二一年三月二十七日 + + </a> + </div> + + <span class="post-date">Mar 27, 2021</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/11/index.html b/archives/page/11/index.html index d21cff73..9cc4648c 100644 --- a/archives/page/11/index.html +++ b/archives/page/11/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2021/03/27/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%80%E5%B9%B4%E4%B8%89%E6%9C%88%E4%BA%8C%E5%8D%81%E4%B8%83%E6%97%A5/"> - - 二零二一年三月二十七日 - - </a> - </div> - - <span class="post-date">Mar 27, 2021</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2021/03/15/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%80%E5%B9%B4%E4%B8%89%E6%9C%88%E5%8D%81%E4%BA%94%E6%97%A5/"> 二零二一年三月十五日 diff --git a/archives/page/2/index.html b/archives/page/2/index.html index e95f3a54..285f0f29 100644 --- a/archives/page/2/index.html +++ b/archives/page/2/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/09/08/%E4%B8%AD%E8%80%81%E5%B9%B4%E4%BA%BA%E6%B2%89%E8%BF%B7%E6%89%8B%E6%9C%BA%E7%9A%84%E9%97%AE%E9%A2%98/"> - - 中老年人沉迷手机的问题 - - </a> - </div> - - <span class="post-date">Sep 8, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/09/07/%E7%BB%99%E5%AD%A9%E5%AD%90%E4%BB%AC%E7%9A%84%E8%AF%9D/"> 什么玩意儿都是 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/06/27/OCaml-News-2024-5/"> + + OCaml News 2024-5 + + </a> + </div> + + <span class="post-date">Jun 27, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/3/index.html b/archives/page/3/index.html index 69b1c77b..5cb425dd 100644 --- a/archives/page/3/index.html +++ b/archives/page/3/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/06/27/OCaml-News-2024-5/"> - - OCaml News 2024-5 - - </a> - </div> - - <span class="post-date">Jun 27, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/06/06/NET-AOT-%E4%B8%8B%E7%9A%84-F-%E5%91%BD%E4%BB%A4%E8%A1%8C%E5%8F%82%E6%95%B0%E8%A7%A3%E6%9E%90%E5%BA%93%E9%80%89%E6%8B%A9/"> .NET AOT 下的 F# 命令行参数解析库选择 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/02/26/OCaml-News-2024-3/"> + + OCaml News 2024-3 + + </a> + </div> + + <span class="post-date">Feb 26, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/4/index.html b/archives/page/4/index.html index b031beec..e10d7532 100644 --- a/archives/page/4/index.html +++ b/archives/page/4/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/02/26/OCaml-News-2024-3/"> - - OCaml News 2024-3 - - </a> - </div> - - <span class="post-date">Feb 26, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/02/07/%E4%BA%8C%E3%80%87%E4%BA%8C%E5%9B%9B%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%B8%83%E6%97%A5/"> 二〇二四年二月七日 @@ -319,6 +301,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/12/01/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%8D%81%E4%BA%8C%E6%9C%88%E4%B8%80%E6%97%A5/"> + + 二〇二三年十二月一日 + + </a> + </div> + + <span class="post-date">Dec 1, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/5/index.html b/archives/page/5/index.html index c93b983d..e736d066 100644 --- a/archives/page/5/index.html +++ b/archives/page/5/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/12/01/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%8D%81%E4%BA%8C%E6%9C%88%E4%B8%80%E6%97%A5/"> - - 二〇二三年十二月一日 - - </a> - </div> - - <span class="post-date">Dec 1, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/11/29/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%8D%81%E4%B8%80%E6%9C%88%E4%BA%8C%E5%8D%81%E4%B9%9D%E6%97%A5/"> 二〇二三年十一月二十九日 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/10/13/%E8%82%9D%E5%8A%9F%E8%83%BD%E6%A3%80%E6%9F%A5%E5%8C%96%E9%AA%8C%E5%8D%95/"> + + 肝功能检查化验单阅读指南 + + </a> + </div> + + <span class="post-date">Oct 13, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/6/index.html b/archives/page/6/index.html index 444b51cf..3642119e 100644 --- a/archives/page/6/index.html +++ b/archives/page/6/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/10/13/%E8%82%9D%E5%8A%9F%E8%83%BD%E6%A3%80%E6%9F%A5%E5%8C%96%E9%AA%8C%E5%8D%95/"> - - 肝功能检查化验单阅读指南 - - </a> - </div> - - <span class="post-date">Oct 13, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/10/12/%E8%A1%80%E5%B8%B8%E8%A7%84%E5%8C%96%E9%AA%8C%E7%BB%93%E6%9E%9C%E9%98%85%E8%AF%BB%E6%8C%87%E5%8D%97/"> 血常规化验结果阅读指南 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/08/01/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%85%AB%E6%9C%88%E4%B8%80%E6%97%A5/"> + + 二〇二三年八月一日 + + </a> + </div> + + <span class="post-date">Aug 1, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/7/index.html b/archives/page/7/index.html index bcb0a4b0..a44950e2 100644 --- a/archives/page/7/index.html +++ b/archives/page/7/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/08/01/%E4%BA%8C%E3%80%87%E4%BA%8C%E4%B8%89%E5%B9%B4%E5%85%AB%E6%9C%88%E4%B8%80%E6%97%A5/"> - - 二〇二三年八月一日 - - </a> - </div> - - <span class="post-date">Aug 1, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/07/30/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%B8%83%E6%9C%88%E4%B8%89%E5%8D%81%E6%97%A5/"> 二零二三年七月三十日 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/05/12/C-20-%E5%AE%9E%E7%8E%B0-string-split/"> + + C++ 20 实现 string split + + </a> + </div> + + <span class="post-date">May 12, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/8/index.html b/archives/page/8/index.html index 14399e7f..ad1bd7a0 100644 --- a/archives/page/8/index.html +++ b/archives/page/8/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/05/12/C-20-%E5%AE%9E%E7%8E%B0-string-split/"> - - C++ 20 实现 string split - - </a> - </div> - - <span class="post-date">May 12, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/05/11/C-vector-%E7%9A%84-push-back-%E5%92%8C-emplace-back/"> C++ vector 的 push_back 和 emplace_back @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/03/14/%E5%91%8B%E5%A1%9E%E7%B1%B3/"> + + 呋塞米 + + </a> + </div> + + <span class="post-date">Mar 14, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/archives/page/9/index.html b/archives/page/9/index.html index bd20877c..4763159c 100644 --- a/archives/page/9/index.html +++ b/archives/page/9/index.html @@ -144,24 +144,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/03/14/%E5%91%8B%E5%A1%9E%E7%B1%B3/"> - - 呋塞米 - - </a> - </div> - - <span class="post-date">Mar 14, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/03/13/%E6%9B%BF%E7%B1%B3%E6%B2%99%E5%9D%A6/"> 替米沙坦 @@ -317,6 +299,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/02/02/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%BA%8C%E6%97%A5/"> + + 二零二三年二月二日 + + </a> + </div> + + <span class="post-date">Feb 2, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/page/5/index.html b/page/5/index.html index b4cfc6df..8bb68a9a 100644 --- a/page/5/index.html +++ b/page/5/index.html @@ -59,7 +59,119 @@ - <meta name="generator" content="Hexo 6.3.0"></head> + <meta name="generator" content="Hexo 6.3.0"><style>mjx-container[jax="SVG"] { + direction: ltr; +} + +mjx-container[jax="SVG"] > svg { + overflow: visible; +} + +mjx-container[jax="SVG"][display="true"] { + display: block; + text-align: center; + margin: 1em 0; +} + +mjx-container[jax="SVG"][justify="left"] { + text-align: left; +} + +mjx-container[jax="SVG"][justify="right"] { + text-align: right; +} + +g[data-mml-node="merror"] > g { + fill: red; + stroke: red; +} + +g[data-mml-node="merror"] > rect[data-background] { + fill: yellow; + stroke: none; +} + +g[data-mml-node="mtable"] > line[data-line] { + stroke-width: 70px; + fill: none; +} + +g[data-mml-node="mtable"] > rect[data-frame] { + stroke-width: 70px; + fill: none; +} + +g[data-mml-node="mtable"] > .mjx-dashed { + stroke-dasharray: 140; +} + +g[data-mml-node="mtable"] > .mjx-dotted { + stroke-linecap: round; + stroke-dasharray: 0,140; +} + +g[data-mml-node="mtable"] > svg { + overflow: visible; +} + +[jax="SVG"] mjx-tool { + display: inline-block; + position: relative; + width: 0; + height: 0; +} + +[jax="SVG"] mjx-tool > mjx-tip { + position: absolute; + top: 0; + left: 0; +} + +mjx-tool > mjx-tip { + display: inline-block; + padding: .2em; + border: 1px solid #888; + font-size: 70%; + background-color: #F8F8F8; + color: black; + box-shadow: 2px 2px 5px #AAAAAA; +} + +g[data-mml-node="maction"][data-toggle] { + cursor: pointer; +} + +mjx-status { + display: block; + position: fixed; + left: 1em; + bottom: 1em; + min-width: 25%; + padding: .2em .4em; + border: 1px solid #888; + font-size: 90%; + background-color: #F8F8F8; + color: black; +} + +foreignObject[data-mjx-xml] { + font-family: initial; + line-height: normal; + overflow: visible; +} + +.MathJax path { + stroke-width: 3; +} + +mjx-container[display="true"] { + overflow: auto hidden; +} + +mjx-container[display="true"] + br { + display: none; +} +</style></head> <body> <div class="mask-border"> </div> @@ -841,128 +841,6 @@ </tags> </entry> <entry> - <title>Generalised signature</title> - <url>/2024/10/18/Generalised-signature/</url> - <content><![CDATA[<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 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="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="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 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="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="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="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="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="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 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="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="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 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 href="https://www.craigfe.io/posts/generalised-signatures#fn-2">2</a> in documentation!</p> -<figure class="highlight ocaml"><table><tr><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="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="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 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 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 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 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="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="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 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 href="https://github.(com/CraigFe/generalised-signatures)"><code>generalised-signatures</code> repository</a>. This repository also contains and a <a 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 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 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 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="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="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 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 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 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 href="https://www.craigfe.io/posts/generalised-signatures#fnref-2">↩</a></li> -</ol> -]]></content> - <tags> - <tag>Technique</tag> - <tag>Archive</tag> - <tag>OCaml</tag> - </tags> - </entry> - <entry> <title>.NET AOT 下的 F# 命令行参数解析库选择</title> <url>/2024/06/06/NET-AOT-%E4%B8%8B%E7%9A%84-F-%E5%91%BD%E4%BB%A4%E8%A1%8C%E5%8F%82%E6%95%B0%E8%A7%A3%E6%9E%90%E5%BA%93%E9%80%89%E6%8B%A9/</url> <content><![CDATA[<p>Argu 不支持 AOT,不过用 F# 的话可以看整个 .NET 的生态,我看了一下 C# 的 CommandLineParser:<br><a href="https://github.com/commandlineparser">https://github.com/commandlineparser</a></p> @@ -2502,19 +2380,6 @@ </categories> </entry> <entry> - <title>二零二三年九月十三日</title> - <url>/2023/09/13/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%B9%9D%E6%9C%88%E5%8D%81%E4%B8%89%E6%97%A5/</url> - <content><![CDATA[<p>“站好! 要拍了啊,倒数三秒,都不要眨眼。” 婚礼结束后, 门口路过的陌生男人拿着相机,充当起了临时的摄影师。</p> -<p>镜头里,她和抱着雪狮的希文站在中间,她手边是依次排开的五个哥哥,希文手边是暮秋, 培元, 世琪, 婧灵五人。<br>在他们后排,其他人也各自找好位置挺直脊背站着。</p> -<p>“拍了啊,倒数,三、二、一……茄子!”</p> -<p>咔擦,画面定格,幸福定格,大家终于从苦难里彻底毕业了。</p> -<p>萤火虫的微光与星空交相辉映,黑夜中潜滋暗长的花香沁人心脾,晚风挠过波光粼粼的海面,彼此相爱的人相拥而眠。</p> -]]></content> - <categories> - <category>gallery</category> - </categories> - </entry> - <entry> <title>二零二三年七月三十日</title> <url>/2023/07/30/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%B8%83%E6%9C%88%E4%B8%89%E5%8D%81%E6%97%A5/</url> <content><![CDATA[<p>那天阳光很好,她想离开病房, 离开躺了快一辈子的病床,她说想晒晒太阳,我带着她去楼下的草坪。她摸摸花,摸摸草,摸摸树。她给自己编了个很好看很好看的辫子,把她摘的花插在上面。可是还没绑好她就垂下了头。</p> @@ -2533,6 +2398,19 @@ </categories> </entry> <entry> + <title>二零二三年九月十三日</title> + <url>/2023/09/13/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%B9%9D%E6%9C%88%E5%8D%81%E4%B8%89%E6%97%A5/</url> + <content><![CDATA[<p>“站好! 要拍了啊,倒数三秒,都不要眨眼。” 婚礼结束后, 门口路过的陌生男人拿着相机,充当起了临时的摄影师。</p> +<p>镜头里,她和抱着雪狮的希文站在中间,她手边是依次排开的五个哥哥,希文手边是暮秋, 培元, 世琪, 婧灵五人。<br>在他们后排,其他人也各自找好位置挺直脊背站着。</p> +<p>“拍了啊,倒数,三、二、一……茄子!”</p> +<p>咔擦,画面定格,幸福定格,大家终于从苦难里彻底毕业了。</p> +<p>萤火虫的微光与星空交相辉映,黑夜中潜滋暗长的花香沁人心脾,晚风挠过波光粼粼的海面,彼此相爱的人相拥而眠。</p> +]]></content> + <categories> + <category>gallery</category> + </categories> + </entry> + <entry> <title>二零二三年二月一日</title> <url>/2023/02/01/%E4%BA%8C%E9%9B%B6%E4%BA%8C%E4%B8%89%E5%B9%B4%E4%BA%8C%E6%9C%88%E4%B8%80%E6%97%A5/</url> <content><![CDATA[<p>我想在六点和日出打招呼,我想去菜市场看看卖蔬菜的阿婆,我想花一上午去准备一餐中午饭,我想下午能在阳台捧着一盏热茶慢慢看书,慢点好,再慢点,慢到能透过阳台栏杆的缝隙看看马路上车水马龙映衬下的老人家提着新鲜的一荤一素慢慢蹒跚走回家,看看贼几把大的夕阳在冒着热气的水杯中慢慢融化。</p> diff --git a/tags/Archive/index.html b/tags/Archive/index.html index e5392e57..a2775650 100644 --- a/tags/Archive/index.html +++ b/tags/Archive/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/"> 10 Tips for Productive FSharp Scripting diff --git a/tags/OCaml/index.html b/tags/OCaml/index.html index bafa6ecd..f131e82c 100644 --- a/tags/OCaml/index.html +++ b/tags/OCaml/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/09/15/Advanced-C-binding-using-ocaml-ctypes-and-dune/"> Advanced C binding using ocaml-ctypes and dune @@ -326,6 +308,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/08/15/poll-error-attribute-in-OCaml/"> + + 使用 [@poll error] 实现线程安全的数据结构 + + </a> + </div> + + <span class="post-date">Aug 15, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/tags/OCaml/page/2/index.html b/tags/OCaml/page/2/index.html index 25e7028f..ff4f3771 100644 --- a/tags/OCaml/page/2/index.html +++ b/tags/OCaml/page/2/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/08/15/poll-error-attribute-in-OCaml/"> - - 使用 [@poll error] 实现线程安全的数据结构 - - </a> - </div> - - <span class="post-date">Aug 15, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/06/28/%E9%9A%90%E8%97%8F%E4%B8%80%E4%BA%9BOCaml-Effect%E7%9A%84%E6%9C%BA%E5%88%B6%EF%BC%8C%E8%AE%A9%E5%85%B6%E8%AF%AD%E6%B3%95%E5%9C%A8%E7%B2%BE%E7%A5%9E%E4%B8%8A%E6%9B%B4%E6%8E%A5%E8%BF%91delimcc/"> 隐藏一些OCaml Effect的机制,让其语法在精神上更接近delimcc diff --git a/tags/Technique/index.html b/tags/Technique/index.html index ae908abc..46c6995d 100644 --- a/tags/Technique/index.html +++ b/tags/Technique/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/10/18/Generalised-signature/"> - - Generalised signature - - </a> - </div> - - <span class="post-date">Oct 18, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/10/18/10-Tips-for-Productive-FSharp-Scripting/"> 10 Tips for Productive FSharp Scripting @@ -324,6 +306,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2024/06/27/OCaml-News-2024-5/"> + + OCaml News 2024-5 + + </a> + </div> + + <span class="post-date">Jun 27, 2024</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/tags/Technique/page/2/index.html b/tags/Technique/page/2/index.html index 6d3d535c..e7ab5fb0 100644 --- a/tags/Technique/page/2/index.html +++ b/tags/Technique/page/2/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2024/06/27/OCaml-News-2024-5/"> - - OCaml News 2024-5 - - </a> - </div> - - <span class="post-date">Jun 27, 2024</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2024/06/06/NET-AOT-%E4%B8%8B%E7%9A%84-F-%E5%91%BD%E4%BB%A4%E8%A1%8C%E5%8F%82%E6%95%B0%E8%A7%A3%E6%9E%90%E5%BA%93%E9%80%89%E6%8B%A9/"> .NET AOT 下的 F# 命令行参数解析库选择 @@ -326,6 +308,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/09/28/A-Brief-History-of-Just-In-Time/"> + + A Brief History of Just-In-Time + + </a> + </div> + + <span class="post-date">Sep 28, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/tags/Technique/page/3/index.html b/tags/Technique/page/3/index.html index e4742b47..c51dd9aa 100644 --- a/tags/Technique/page/3/index.html +++ b/tags/Technique/page/3/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/09/28/A-Brief-History-of-Just-In-Time/"> - - A Brief History of Just-In-Time - - </a> - </div> - - <span class="post-date">Sep 28, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/08/15/tick-thread%E5%9C%A8Multicore-OCaml%E4%B8%AD%E7%9A%84%E4%BD%9C%E7%94%A8/"> tick thread在Multicore OCaml中的作用 @@ -324,6 +306,24 @@ </div> + + + + + + <div class="post-list-item"> + <div class="post-title"> + <a href="/2023/05/03/Rust-NewType-%E6%A8%A1%E5%BC%8F/"> + + Rust NewType 模式 + + </a> + </div> + + <span class="post-date">May 3, 2023</span> + </div> + + <div id="paginator"> <div class=paginator> diff --git a/tags/Technique/page/4/index.html b/tags/Technique/page/4/index.html index c478b65b..817eef77 100644 --- a/tags/Technique/page/4/index.html +++ b/tags/Technique/page/4/index.html @@ -151,24 +151,6 @@ <div class="post-list-item"> <div class="post-title"> - <a href="/2023/05/03/Rust-NewType-%E6%A8%A1%E5%BC%8F/"> - - Rust NewType 模式 - - </a> - </div> - - <span class="post-date">May 3, 2023</span> - </div> - - - - - - - - <div class="post-list-item"> - <div class="post-title"> <a href="/2023/05/02/Rust-Partial-%E8%AF%AD%E4%B9%89/"> Rust Partial 语义 |
