Re: [Haskell-cafe] Higher-order algorithms

(Accidentally sent off-list, resending)

On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov 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

On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin wrote: 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