[Haskell-cafe] Richard Bird and the fast nub function

[Jason Dagit]

On Sun, Sep 29, 2013 at 1:40 PM, Henning Thielemann <
lemming at henning-thielemann.de> wrote:

>
> In Richard Bird's "Functional Pearls in Algorithm Design" there is chapter
> 10 "Removing duplicates" which is about a fast and sorting variant of
> 'nub'. After reading the introduction of the chapter I answered mentally
> "Set.toAscList . Set.fromList - next chapter please". However after the
> introduction eight pages follow that develop an efficient algorithm for the
> problem. I suspected there might be the additional difficulty of not using
> the standard Set type, however on page 70 the common Set API is "imported".
> In the final remarks of the chapter Bird writes: "A nagging doubt remains
> that there might be a much simpler solution to such a simply stated
> problem. But so far I have not been able to find one." Now I am lost. Can
> someone tell me, how the task differs from what "Set.toAscList .
> Set.fromList" does?
>

I've been puzzling over this too. The most convincing answer I've come up
with (and it's not very convincing) is that he presented the development
because he aims to teach the process and the skill, not because it lead to
a particularly efficient implementation in this case.

In fact, when folks were talking about improving `nub` on here a few months
ago I finally got around to benchmarking it and found that it wasn't all
that efficient compared to the other proposals. I don't think I have the
numbers anymore. It wasn't terrible but it wasn't amazing either.

So yeah, I don't know what to make of that chapter :(

Jason
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130929/664db230/attachment.htm>