[GHC] #1218: Add sortNub and sortNubBy to Data.List

[Lennart Augustsson]

That would actually be wrong.  It's easy to come up with examples  
where this "identity" is false.

For instance:

data T = T Int Int deriving (Ord, Show)
instance Eq T where
     T x _ == T y _ =  x == y

ts = [T 1 1, T 1 undefined]


On Mar 18, 2007, at 23:51 , GHC wrote:

> #1218: Add sortNub and sortNubBy to Data.List
> ---------------------------- 
> +-----------------------------------------------
>  Reporter:  neil            |          Owner:
>      Type:  proposal        |         Status:  new
>  Priority:  normal          |      Milestone:  Not GHC
> Component:  libraries/base  |        Version:
>  Severity:  normal          |     Resolution:
>  Keywords:                  |     Difficulty:  Unknown
>  Testcase:                  |   Architecture:  Unknown
>        Os:  Unknown         |
> ---------------------------- 
> +-----------------------------------------------
> Comment (by dons):
>
>  How about rather than changing the api, purely for efficiency  
> reasons, we
>  just add a rewrite rule to Data.List for this optimisation?
>
>  The rule would be:
>
>  {{{
>  {-# RULES
>  "sort/nub" sort . nub = map head . group . sort
>    #-}
>  }}}
>
>  sort . nub will be rewritten to the optimised case, and we won't  
> need to
>  further complicate the API.
>
>  Quite often now it is possible for the library author to expose  
> only a
>  small, generic API, while providing internal rules for specific  
> optimised
>  cases. This keeps the interface small, while still providing  
> performance.
>
>  Data.ByteString does this in a number of places, for example:
>
>  {{{
>  {-# RULES
>    "FPS specialise filter (== x)" forall x.
>       filter (== x) = filterByte x
>    #-}
>  }}}
>
>  I'd really not like to see more functions exposed in the list  
> interface,
>  only as optimisations, that could be better provided via RULES.
>
> -- 
> Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/1218>
> GHC <http://www.haskell.org/ghc/>
> The Glasgow Haskell  
> Compiler_______________________________________________
> Glasgow-haskell-bugs mailing list
> Glasgow-haskell-bugs at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs