[Haskell-cafe] Higher-order algorithms
max.rabkin at gmail.com
Mon Aug 23 12:10:49 EDT 2010
(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` 
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.
More information about the Haskell-Cafe