[trac@galois.com: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List]

[Lennart Augustsson]

As I pointed out in the GHC trac report, this rule is wrong.  E.g.,

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 19, 2007, at 00:02 , Donald Bruce Stewart wrote:

>
> I propose we *do not* change the api to add the special case:
>
>     sortNub = sort . nub
>             = map head . group . sort
>
> and instead add a rewrite rule to Data.List to provide this
> optimisation.
>
>  {-# RULES
>  "sort/nub" sort . nub = map head . group . sort
>    #-}
>
> Along with a QuickCheck property to test it:
>
>  prop_sortnub xs = sort (nub xs) == map head (group (sort xs))
>
> -- Don
>
> ----- Forwarded message from GHC <trac at galois.com> -----
>
> Date: Sun, 18 Mar 2007 23:51:50 -0000
> From: GHC <trac at galois.com>
> To: glasgow-haskell-bugs at haskell.org
> Subject: Re: [GHC] #1218: Add sortNub and sortNubBy to Data.List
>
> #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
>
>
> ----- End forwarded message -----
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries