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

David Fletcher david at bubblycloud.com
Sun Sep 29 23:12:27 CEST 2013

On Sun, 29 Sep 2013 21:40:28 +0100, 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?

It asks for the lexicographically least solution that is still an actual
subsequence, i.e. still in the order it appears in the input.

He gives the example that input "calculus" "aclus".  Your way would
give "aclsu".

More information about the Haskell-Cafe mailing list