Data/Function.hs

   1 -----------------------------------------------------------------------------
   2 -- |
   3 -- Module      :  Data.Function
   4 -- Copyright   :  Nils Anders Danielsson 2006
   5 -- License     :  BSD-style (see the LICENSE file in the distribution)
   6 --
   7 -- Maintainer  :  libraries@haskell.org
   8 -- Stability   :  experimental
   9 -- Portability :  portable
  10 --
  11 -- Simple combinators working solely on and with functions.
  12
  13 module Data.Function
  14   ( -- * "Prelude" re-exports
  15     id, const, (.), flip, ($)
  16     -- * Other combinators
  17   , fix
  18   , on
  19   ) where
  20
  21 import Prelude
  22
  23 infixl 0 `on`
  24
  25 -- | @'fix' f@ is the least fixed point of the function @f@,
  26 -- i.e. the least defined @x@ such that @f x = x@.
  27 fix :: (a -> a) -> a
  28 fix f = let x = f x in x
  29
  30 -- | @(*) \`on\` f = \\x y -> f x * f y@.
  31 --
  32 -- Typical usage: @'Data.List.sortBy' ('compare' \`on\` 'fst')@.
  33 --
  34 -- Algebraic properties:
  35 --
  36 -- * @(*) \`on\` 'id' = (*)@ (if @(*) &#x2209; {&#x22a5;, 'const' &#x22a5;}@)
  37 --
  38 -- * @((*) \`on\` f) \`on\` g = (*) \`on\` (f . g)@
  39 --
  40 -- * @'flip' on f . 'flip' on g = 'flip' on (g . f)@
  41
  42 -- Proofs (so that I don't have to edit the test-suite):
  43
  44 --   (*) `on` id
  45 -- =
  46 --   \x y -> id x * id y
  47 -- =
  48 --   \x y -> x * y
  49 -- = { If (*) /= _|_ or const _|_. }
  50 --   (*)
  51
  52 --   (*) `on` f `on` g
  53 -- =
  54 --   ((*) `on` f) `on` g
  55 -- =
  56 --   \x y -> ((*) `on` f) (g x) (g y)
  57 -- =
  58 --   \x y -> (\x y -> f x * f y) (g x) (g y)
  59 -- =
  60 --   \x y -> f (g x) * f (g y)
  61 -- =
  62 --   \x y -> (f . g) x * (f . g) y
  63 -- =
  64 --   (*) `on` (f . g)
  65 -- =
  66 --   (*) `on` f . g
  67
  68 --   flip on f . flip on g
  69 -- =
  70 --   (\h (*) -> (*) `on` h) f . (\h (*) -> (*) `on` h) g
  71 -- =
  72 --   (\(*) -> (*) `on` f) . (\(*) -> (*) `on` g)
  73 -- =
  74 --   \(*) -> (*) `on` g `on` f
  75 -- = { See above. }
  76 --   \(*) -> (*) `on` g . f
  77 -- =
  78 --   (\h (*) -> (*) `on` h) (g . f)
  79 -- =
  80 --   flip on (g . f)
  81
  82 on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
  83 (.*.) `on` f = \x y -> f x .*. f y