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

[Donald Bruce Stewart]

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