<br><div class="gmail_quote">On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin <span dir="ltr">&lt;<a href="mailto:max.rabkin@gmail.com">max.rabkin@gmail.com</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

(Accidentally sent off-list, resending)<br>
<br>
On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov &lt;<a href="mailto:ekirpichov@gmail.com">ekirpichov@gmail.com</a>&gt; wrote:<br>
&gt; * Difference lists<br>
<div class="im"><br>
&gt; I mean that not only higher-order facilities are used, but the essence<br>
&gt; of the algorithm is some non-trivial higher-order manipulation.<br>
<br>
</div>If I&#39;m not mistaken, we can &quot;defunctionalize&quot; difference lists like this:<br>
<br>
data DList a = Chunk [a] | Concat (DList a) (DList a)<br>
<br>
fromList = Chunk<br>
(&lt;&gt;) = Concat<br>
singleton = Chunk . (:[])<br>
empty = Chunk []<br>
<br>
toList dl = dl `fold` []<br>
 where<br>
   infixr `fold`<br>
   fold :: DList a -&gt; [a] -&gt; [a]<br>
   fold (Concat l r) ys = l `fold` r `fold` ys<br>
   fold (Chunk xs) ys = xs ++ ys<br>
<br>
(This implementation has only been lightly tested)<br>
<br>
And of course, we knew this was possible, since we can compile DLists<br>
to first-order machines.<br>
<br>
I agree that the functional, higher-order presentation is clear and<br>
elegant. But is it essential?<br>
<br></blockquote><div>It&#39;s true that any higher-order program can be defunctionalized (or closure-converted) to a first order program. But defunctionalization is a whole program transformation and in general we might lose compositionality when applying it to a library. In your case above with difference lists there is no change in the interface since it is first order. But if you try to defunctionalize a monad then you will have to defunctionalize the second argument to the bind function and all of a sudden you cannot use the bind function as freely as before. </div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Also, I&#39;m curious about how this performs relative to the functional version.<br>
<font color="#888888"><font class="Apple-style-span" color="#000000"><font class="Apple-style-span" color="#888888"><br></font></font></font></blockquote><div>In my small experiments with defunctionalization there is not much difference between a higher order program and its defunctionalized version. I used GHC in those experiments.</div>

<div><br></div><div>Cheers,</div><div><br></div><div>Josef </div></div>