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

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

Date: Sun, 18 Mar 2007 23:51:50 -0000 From: GHC To: glasgow-haskell-bugs@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@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs

----- End forwarded message ----- _______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries