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

Henning Thielemann lemming at henning-thielemann.de
Sun Sep 29 22:40:28 CEST 2013


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?



More information about the Haskell-Cafe mailing list