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

[David Fletcher]

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".