[Haskell-cafe] Higher-order algorithms

[Max Rabkin]

(Accidentally sent off-list, resending)

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

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

--Max