<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta name="robots" content="index,nofollow">
<title>Fold01N - MLton Standard ML Compiler (SML Compiler)</title>
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="all" href="common.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="screen" href="screen.css">
<link rel="stylesheet" type="text/css" charset="iso-8859-1" media="print" href="print.css">
<link rel="Start" href="Home">
</head>
<body lang="en" dir="ltr">
<script src="http://www.google-analytics.com/urchin.js" type="text/javascript">
</script>
<script type="text/javascript">
_uacct = "UA-833377-1";
urchinTracker();
</script>
<table bgcolor = lightblue cellspacing = 0 style = "border: 0px;" width = 100%>
<tr>
<td style = "
border: 0px;
color: darkblue;
font-size: 150%;
text-align: left;">
<a class = mltona href="Home">MLton MLTONWIKIVERSION</a>
<td style = "
border: 0px;
font-size: 150%;
text-align: center;
width: 50%;">
Fold01N
<td style = "
border: 0px;
text-align: right;">
<table cellspacing = 0 style = "border: 0px">
<tr style = "vertical-align: middle;">
</table>
<tr style = "background-color: white;">
<td colspan = 3
style = "
border: 0px;
font-size:70%;
text-align: right;">
<a href = "Home">Home</a>
<a href = "TitleIndex">Index</a>
</table>
<div id="content" lang="en" dir="ltr">
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, <tt>Fold01N</tt>, that solves the problem once and for all, and eases the definition of such functions.
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Fold01N =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">fun</FONT></B> fold {finish, start, zero} =
Fold.fold ((id, finish, <B><FONT COLOR="#A020F0">fn</FONT></B> () => zero, start),
<B><FONT COLOR="#A020F0">fn</FONT></B> (finish, _, p, _) => finish (p ()))
<B><FONT COLOR="#A020F0">fun</FONT></B> step0 {combine, input} =
Fold.step0 (<B><FONT COLOR="#A020F0">fn</FONT></B> (_, finish, _, f) =>
(finish,
finish,
<B><FONT COLOR="#A020F0">fn</FONT></B> () => f input,
<B><FONT COLOR="#A020F0">fn</FONT></B> x' => combine (f input, x')))
<B><FONT COLOR="#A020F0">fun</FONT></B> step1 {combine} z input =
step0 {combine = combine, input = input} z
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
<p>
If one has a value <tt>zero</tt>, and functions <tt>start</tt>, <tt>c</tt>, and <tt>finish</tt>, then one can define a variable-arity function <tt>f</tt> and stepper <tt>`</tt> as follows.
</p>
<pre class=code>
<B><FONT COLOR="#A020F0">val</FONT></B> f = <B><FONT COLOR="#A020F0">fn</FONT></B> z => Fold01N.fold {finish = finish, start = start, zero = zero} z
<B><FONT COLOR="#A020F0">val</FONT></B> ` = <B><FONT COLOR="#A020F0">fn</FONT></B> z => Fold01N.step1 {combine = c} z
</PRE>
<p>
</p>
<p>
One can then use the fold equation to prove the following equations.
<pre class=code>
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))
...
</PRE>
</p>
<p>
For an example of <tt>Fold01N</tt>, see <a href="VariableArityPolymorphism">VariableArityPolymorphism</a>.
</p>
<h2 id="head-c8f728eef389fe7d14bbb9f38f947c3019d75348">Typing Fold01N</h2>
<p>
Here is the signature for <tt>Fold01N</tt>. 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 <tt>open</tt> in the full structure.
</p>
<pre class=code>
<B><FONT COLOR="#0000FF">structure</FONT></B> Fold01N =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('input, 'accum1, 'accum2, 'answer, 'zero,
'a, 'b, 'c, 'd, 'e) t </FONT></B>=<B><FONT COLOR="#228B22">
(('zero -> 'zero)
* ('accum2 -> 'answer)
* (unit -> 'zero)
* ('input -> 'accum1),
('a -> 'b) * 'c * (unit -> 'a) * 'd,
'b,
'e) Fold.t
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('input1, 'accum1, 'input2, 'accum2,
'a, 'b, 'c, 'd, 'e, 'f) step0 </FONT></B>=<B><FONT COLOR="#228B22">
('a * 'b * 'c * ('input1 -> 'accum1),
'b * 'b * (unit -> 'accum1) * ('input2 -> 'accum2),
'd, 'e, 'f) Fold.step0
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('accum1, 'input, 'accum2,
'a, 'b, 'c, 'd, 'e, 'f, 'g) step1 </FONT></B>=<B><FONT COLOR="#228B22">
('a,
'b * 'c * 'd * ('a -> 'accum1),
'c * 'c * (unit -> 'accum1) * ('input -> 'accum2),
'e, 'f, 'g) Fold.step1
</FONT></B><B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#0000FF">signature</FONT></B> FOLD_01N =
<B><FONT COLOR="#0000FF">sig</FONT></B>
<B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) t </FONT></B>=<B><FONT COLOR="#228B22">
('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.t
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) step0 </FONT></B>=<B><FONT COLOR="#228B22">
('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.step0
</FONT></B><B><FONT COLOR="#A020F0">type</FONT></B><B><FONT COLOR="#228B22"> ('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) step1 </FONT></B>=<B><FONT COLOR="#228B22">
('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j) Fold01N.step1
</FONT></B><B><FONT COLOR="#A020F0">val</FONT></B> fold:
{finish: 'accum2 -> 'answer,
start: 'input -> 'accum1,
zero: 'zero}
-> ('input, 'accum1, 'accum2, 'answer, 'zero,
'a, 'b, 'c, 'd, 'e) t
<B><FONT COLOR="#A020F0">val</FONT></B> step0:
{combine: 'accum1 * 'input2 -> 'accum2,
input: 'input1}
-> ('input1, 'accum1, 'input2, 'accum2,
'a, 'b, 'c, 'd, 'e, 'f) step0
<B><FONT COLOR="#A020F0">val</FONT></B> step1:
{combine: 'accum1 * 'input -> 'accum2}
-> ('accum1, 'input, 'accum2,
'a, 'b, 'c, 'd, 'e, 'f, 'g) step1
<B><FONT COLOR="#0000FF">end</FONT></B>
<B><FONT COLOR="#0000FF">structure</FONT></B> Fold01N: FOLD_01N =
<B><FONT COLOR="#0000FF">struct</FONT></B>
<B><FONT COLOR="#0000FF">open</FONT></B> Fold01N
<B><FONT COLOR="#A020F0">fun</FONT></B> fold {finish, start, zero} =
Fold.fold ((id, finish, <B><FONT COLOR="#A020F0">fn</FONT></B> () => zero, start),
<B><FONT COLOR="#A020F0">fn</FONT></B> (finish, _, p, _) => finish (p ()))
<B><FONT COLOR="#A020F0">fun</FONT></B> step0 {combine, input} =
Fold.step0 (<B><FONT COLOR="#A020F0">fn</FONT></B> (_, finish, _, f) =>
(finish,
finish,
<B><FONT COLOR="#A020F0">fn</FONT></B> () => f input,
<B><FONT COLOR="#A020F0">fn</FONT></B> x' => combine (f input, x')))
<B><FONT COLOR="#A020F0">fun</FONT></B> step1 {combine} z input =
step0 {combine = combine, input = input} z
<B><FONT COLOR="#0000FF">end</FONT></B>
</PRE>
<p>
</p>
</div>
<p>
<hr>
Last edited on 2006-03-21 23:10:39 by <span title="cs180212.pp.htv.fi"><a href="VesaKarvonen">VesaKarvonen</a></span>.
</body></html>
