<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta name="generator" content="Asciidoctor 2.0.26">
<title>Fold01N</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Open+Sans:300,300italic,400,400italic,600,600italic%7CNoto+Serif:400,400italic,700,700italic%7CDroid+Sans+Mono:400,700">
<link rel="stylesheet" href="./asciidoctor.css">
<link rel="stylesheet" href="./mlton.css">

</head>
<body class="article">
<div id="mlton-header">
<div id="mlton-header-text">
<h2>
<a href="./Home">
MLton
20241230+git20251029+dfsg-5
</a>
</h2>
</div>
</div>
<div id="header">
<h1>Fold01N</h1>
</div>
<div id="content">
<div id="preamble">
<div class="sectionbody">
<div class="paragraph">
<p>A common use pattern of <a href="Fold">Fold</a> is to define a variable-arity
function that combines multiple arguments together using a binary
function.  It is slightly tricky to do this directly using fold,
because of the special treatment required for the case of zero or one
argument.  Here is a structure, <code>Fold01N</code>, that solves the problem
once and for all, and eases the definition of such functions.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">structure Fold01N =
   struct
      fun fold {finish, start, zero} =
         Fold.fold ((id, finish, fn () =&gt; zero, start),
                    fn (finish, _, p, _) =&gt; finish (p ()))

      fun step0 {combine, input} =
         Fold.step0 (fn (_, finish, _, f) =&gt;
                     (finish,
                      finish,
                      fn () =&gt; f input,
                      fn x' =&gt; combine (f input, x')))

      fun step1 {combine} z input =
         step0 {combine = combine, input = input} z
   end</code></pre>
</div>
</div>
<div class="paragraph">
<p>If one has a value <code>zero</code>, and functions <code>start</code>, <code>c</code>, and <code>finish</code>,
then one can define a variable-arity function <code>f</code> and stepper
<code>`</code> as follows.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">val f = fn z =&gt; Fold01N.fold {finish = finish, start = start, zero = zero} z
val ` = fn z =&gt; Fold01N.step1 {combine = c} z</code></pre>
</div>
</div>
<div class="paragraph">
<p>One can then use the fold equation to prove the following equations.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">f $ = zero
f `a1 $ = finish (start a1)
f `a1 `a2 $ = finish (c (start a1, a2))
f `a1 `a2 `a3 $ = finish (c (c (start a1, a2), a3))
...</code></pre>
</div>
</div>
<div class="paragraph">
<p>For an example of <code>Fold01N</code>, see <a href="VariableArityPolymorphism">VariableArityPolymorphism</a>.</p>
</div>
</div>
</div>
<div class="sect1">
<h2 id="_typing_fold01n">Typing Fold01N</h2>
<div class="sectionbody">
<div class="paragraph">
<p>Here is the signature for <code>Fold01N</code>.  We use a trick to avoid having
to duplicate the definition of some rather complex types in both the
signature and the structure.  We first define the types in a
structure.  Then, we define them via type re-definitions in the
signature, and via <code>open</code> in the full structure.</p>
</div>
<div class="listingblock">
<div class="content">
<pre class="rouge highlight"><code data-lang="sml">structure Fold01N =
   struct
      type ('input, 'accum1, 'accum2, 'answer, 'zero,
            'a, 'b, 'c, 'd, 'e) t =
         (('zero -&gt; 'zero)
          * ('accum2 -&gt; 'answer)
          * (unit -&gt; 'zero)
          * ('input -&gt; 'accum1),
          ('a -&gt; 'b) * 'c * (unit -&gt; 'a) * 'd,
          'b,
          'e) Fold.t

       type ('input1, 'accum1, 'input2, 'accum2,
            'a, 'b, 'c, 'd, 'e, 'f) step0 =
         ('a * 'b * 'c * ('input1 -&gt; 'accum1),
          'b * 'b * (unit -&gt; 'accum1) * ('input2 -&gt; 'accum2),
          'd, 'e, 'f) Fold.step0

      type ('accum1, 'input, 'accum2,
            'a, 'b, 'c, 'd, 'e, 'f, 'g) step1 =
         ('a,
          'b * 'c * 'd * ('a -&gt; 'accum1),
          'c * 'c * (unit -&gt; 'accum1) * ('input -&gt; 'accum2),
          'e, 'f, 'g) Fold.step1
   end

signature FOLD_01N =
   sig
      type ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) t =
         ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.t
      type ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) step0 =
         ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.step0
      type ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) step1 =
         ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.step1

      val fold:
         {finish: 'accum2 -&gt; 'answer,
          start: 'input -&gt; 'accum1,
          zero: 'zero}
         -&gt; ('input, 'accum1, 'accum2, 'answer, 'zero,
             'a, 'b, 'c, 'd, 'e) t

      val step0:
         {combine: 'accum1 * 'input2 -&gt; 'accum2,
          input: 'input1}
         -&gt; ('input1, 'accum1, 'input2, 'accum2,
             'a, 'b, 'c, 'd, 'e, 'f) step0

      val step1:
         {combine: 'accum1 * 'input -&gt; 'accum2}
         -&gt; ('accum1, 'input, 'accum2,
             'a, 'b, 'c, 'd, 'e, 'f, 'g) step1
   end

structure Fold01N: FOLD_01N =
   struct
      open Fold01N

      fun fold {finish, start, zero} =
         Fold.fold ((id, finish, fn () =&gt; zero, start),
                    fn (finish, _, p, _) =&gt; finish (p ()))

      fun step0 {combine, input} =
         Fold.step0 (fn (_, finish, _, f) =&gt;
                     (finish,
                      finish,
                      fn () =&gt; f input,
                      fn x' =&gt; combine (f input, x')))

      fun step1 {combine} z input =
         step0 {combine = combine, input = input} z
   end</code></pre>
</div>
</div>
</div>
</div>
</div>
</body>
</html>