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