On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin <max.rabkin@gmail.com> wrote:

(Accidentally sent off-list, resending)

On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov <ekirpichov@gmail.com> wrote:
> * Difference lists

> I mean that not only higher-order facilities are used, but the essence
> of the algorithm is some non-trivial higher-order manipulation.

If I'm not mistaken, we can "defunctionalize" difference lists like this:

data DList a = Chunk [a] | Concat (DList a) (DList a)

fromList = Chunk
(<>) = Concat
singleton = Chunk . (:[])
empty = Chunk []

toList dl = dl `fold` []
where
infixr `fold`
fold :: DList a -> [a] -> [a]
fold (Concat l r) ys = l `fold` r `fold` ys
fold (Chunk xs) ys = xs ++ ys

(This implementation has only been lightly tested)

And of course, we knew this was possible, since we can compile DLists
to first-order machines.

I agree that the functional, higher-order presentation is clear and
elegant. But is it essential?

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.

Also, I'm curious about how this performs relative to the functional version.

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.

Cheers,

Josef