[Haskell-cafe] ordNub

[Andreas Abel]

On 14.07.2013 13:20, Niklas Hambüchen wrote:
> I've taken the Ord-based O(n * log n) implementation from yi using a Set:
>
>    ordNub :: (Ord a) => [a] -> [a]
>    ordNub l = go empty l
>      where
>        go _ []     = []
>        go s (x:xs) = if x `member` s then go s xs
>                                      else x : go (insert x s) xs
>
> (The benchmark also shows some other potential problem: Using a state
> monad to keep the set instead of a function argument can be up to 20
> times slower. Should that happen?)

I cannot say whether this should happen, but your code about can be 
straight-forwardly refactored using a *Reader* monad.

import Control.Monad.Reader

import Data.Functor ((<$>))
import qualified Data.Set as Set

-- ifM still not in Control.Monad
ifM mc md me = do { c <- mc; if c then md else me }

ordNub :: (Ord a) => [a] -> [a]
ordNub l = runReader (go l) Set.empty
   where
     go []     = return []
     go (x:xs) = ifM ((x `Set.member`) <$> ask)
                     (go xs)
                     ((x :) <$> local (Set.insert x) (go xs))

test = ordNub [1,2,4,1,3,5,2,3,4,5,6,1]

Of course, this does not lend itself to an application of filterM.

In fact, your implementation is already in the (Set a ->) reader monad, 
in normalized form.  It looks already optimal to me.

Cheers,
Andreas

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/