<br><div class="gmail_quote">On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin <span dir="ltr"><<a href="mailto:max.rabkin@gmail.com">max.rabkin@gmail.com</a>></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 <<a href="mailto:ekirpichov@gmail.com">ekirpichov@gmail.com</a>> wrote:<br>
> * Difference lists<br>
<div class="im"><br>
> I mean that not only higher-order facilities are used, but the essence<br>
> of the algorithm is some non-trivial higher-order manipulation.<br>
<br>
</div>If I'm not mistaken, we can "defunctionalize" difference lists like this:<br>
<br>
data DList a = Chunk [a] | Concat (DList a) (DList a)<br>
<br>
fromList = Chunk<br>
(<>) = Concat<br>
singleton = Chunk . (:[])<br>
empty = Chunk []<br>
<br>
toList dl = dl `fold` []<br>
where<br>
infixr `fold`<br>
fold :: DList a -> [a] -> [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'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'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>