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