On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin <[email protected]> wrote:
> (Accidentally sent off-list, resending) > > On Mon, Aug 23, 2010 at 15:03, Eugene Kirpichov <[email protected]> > 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
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
