On Sun, Sep 29, 2013 at 1:40 PM, Henning Thielemann < lemming@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