1de5eac4692d639f5c91d431dc7786fbf18a5857
[packages/base.git] / 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 , on
18 ) where
19
20 import Prelude
21
22 infixl 0 `on`
23
24 -- | @(*) \`on\` f = \\x y -> f x * f y@.
25 --
26 -- Typical usage: @'Data.List.sortBy' ('compare' \`on\` 'fst')@.
27 --
28 -- Algebraic properties:
29 --
30 -- * @(*) \`on\` 'id' = (*)@ (if @(*) ∉ {⊥, 'const' ⊥}@)
31 --
32 -- * @((*) \`on\` f) \`on\` g = (*) \`on\` (f . g)@
33 --
34 -- * @'flip' on f . 'flip' on g = 'flip' on (g . f)@
35
36 -- Proofs (so that I don't have to edit the test-suite):
37
38 -- (*) `on` id
39 -- =
40 -- \x y -> id x * id y
41 -- =
42 -- \x y -> x * y
43 -- = { If (*) /= _|_ or const _|_. }
44 -- (*)
45
46 -- (*) `on` f `on` g
47 -- =
48 -- ((*) `on` f) `on` g
49 -- =
50 -- \x y -> ((*) `on` f) (g x) (g y)
51 -- =
52 -- \x y -> (\x y -> f x * f y) (g x) (g y)
53 -- =
54 -- \x y -> f (g x) * f (g y)
55 -- =
56 -- \x y -> (f . g) x * (f . g) y
57 -- =
58 -- (*) `on` (f . g)
59 -- =
60 -- (*) `on` f . g
61
62 -- flip on f . flip on g
63 -- =
64 -- (\h (*) -> (*) `on` h) f . (\h (*) -> (*) `on` h) g
65 -- =
66 -- (\(*) -> (*) `on` f) . (\(*) -> (*) `on` g)
67 -- =
68 -- \(*) -> (*) `on` g `on` f
69 -- = { See above. }
70 -- \(*) -> (*) `on` g . f
71 -- =
72 -- (\h (*) -> (*) `on` h) (g . f)
73 -- =
74 -- flip on (g . f)
75
76 on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
77 (*) `on` f = \x y -> f x * f y