[Haskell-cafe] sortBy2 for List library

[Serge D. Mechveliani]

Consider the following suggestions for the standard Haskell library
`List'.

------------------------------------------------------------------------
import List (intersprerse, insertBy)

compose :: [a -> a] -> a -> a     -- just appropriate name
compose =  foldr (.) id

insertBy2 :: (a -> b) -> Comparison b -> a -> [a] -> [a]
insertBy2    f           cp              a    xs  =

  map fst $ insertBy (\ p p' -> cp (snd p) (snd p'))
                                           (a, f a) [(x, f x) | x <- xs]

Similar are  mergeBy2, sortBy2.

type ComparisonValue = LT | GT | Eq  deriving ... 
                                          -- better name than `Ordering'

type Comparison a    = a -> a -> ComparisonValue 
------------------------------------------------------------------------


Motivation example for `compose':

  myShowsList :: Show a => [a] -> String -> String
  myShowsList              xs  =
                          compose $ intersperse (",  "++) $ map shows xs

  myShowsList (";  "++) [1,2,3] -->  "1;  2;  3"


Motivation example for  insertBy2:
Consider the program 
                insertBy (\ n m -> compare (f n) (f m)) 100 [0 .. 1000],

where  f :: Integer -> Integer  is expensive to compute.
We see that the program
                        insertBy2 f compare 100 [1 .. 1000]

spends 2 times less of `f' invocations, and looks natural.

-----------------
Serge Mechveliani
mechvel at botik.ru