[Haskell-cafe] Higher-order algorithms

[Josef Svenningsson]

On Mon, Aug 23, 2010 at 6:10 PM, Max Rabkin <max.rabkin at gmail.com> wrote:

> (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?
>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100824/35d65d9d/attachment.html