(Accidentally sent off-list, resending) On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov <ekirpic...@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
