1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# OPTIONS_HADDOCK print-explicit-runtime-reps #-}
-- Show the levity-polymorphic signature of '$'
-----------------------------------------------------------------------------
-- |
-- Module : Data.Function
-- Copyright : Nils Anders Danielsson 2006
-- , Alexander Berntsen 2014
-- License : BSD-style (see the LICENSE file in the distribution)
--
-- Maintainer : libraries@haskell.org
-- Stability : stable
-- Portability : portable
--
-- Simple combinators working solely on and with functions.
--
-----------------------------------------------------------------------------
module Data.Function
( -- * "Prelude" re-exports
id, const, (.), flip, ($)
-- * Other combinators
, (&)
, fix
, on
, applyWhen
) where
import GHC.Base ( ($), (.), id, const, flip )
import Data.Bool ( Bool(..) )
infixl 0 `on`
infixl 1 &
-- | @'fix' f@ is the least fixed point of the function @f@,
-- i.e. the least defined @x@ such that @f x = x@.
--
-- For example, we can write the factorial function using direct recursion as
--
-- >>> let fac n = if n <= 1 then 1 else n * fac (n-1) in fac 5
-- 120
--
-- This uses the fact that Haskell’s @let@ introduces recursive bindings. We can
-- rewrite this definition using 'fix',
--
-- >>> fix (\rec n -> if n <= 1 then 1 else n * rec (n-1)) 5
-- 120
--
-- Instead of making a recursive call, we introduce a dummy parameter @rec@;
-- when used within 'fix', this parameter then refers to 'fix'’s argument, hence
-- the recursion is reintroduced.
fix :: (a -> a) -> a
fix f = let x = f x in x
-- | @'on' b u x y@ runs the binary function @b@ /on/ the results of applying
-- unary function @u@ to two arguments @x@ and @y@. From the opposite
-- perspective, it transforms two inputs and combines the outputs.
--
-- @((+) \``on`\` f) x y = f x + f y@
--
-- Typical usage: @'Data.List.sortBy' ('Prelude.compare' \`on\` 'Prelude.fst')@.
--
-- Algebraic properties:
--
-- * @(*) \`on\` 'id' = (*) -- (if (*) ∉ {⊥, 'const' ⊥})@
--
-- * @((*) \`on\` f) \`on\` g = (*) \`on\` (f . g)@
--
-- * @'flip' on f . 'flip' on g = 'flip' on (g . f)@
on :: (b -> b -> c) -> (a -> b) -> a -> a -> c
(.*.) `on` f = \x y -> f x .*. f y
-- Proofs (so that I don't have to edit the test-suite):
-- (*) `on` id
-- =
-- \x y -> id x * id y
-- =
-- \x y -> x * y
-- = { If (*) /= _|_ or const _|_. }
-- (*)
-- (*) `on` f `on` g
-- =
-- ((*) `on` f) `on` g
-- =
-- \x y -> ((*) `on` f) (g x) (g y)
-- =
-- \x y -> (\x y -> f x * f y) (g x) (g y)
-- =
-- \x y -> f (g x) * f (g y)
-- =
-- \x y -> (f . g) x * (f . g) y
-- =
-- (*) `on` (f . g)
-- =
-- (*) `on` f . g
-- flip on f . flip on g
-- =
-- (\h (*) -> (*) `on` h) f . (\h (*) -> (*) `on` h) g
-- =
-- (\(*) -> (*) `on` f) . (\(*) -> (*) `on` g)
-- =
-- \(*) -> (*) `on` g `on` f
-- = { See above. }
-- \(*) -> (*) `on` g . f
-- =
-- (\h (*) -> (*) `on` h) (g . f)
-- =
-- flip on (g . f)
-- | '&' is a reverse application operator. This provides notational
-- convenience. Its precedence is one higher than that of the forward
-- application operator '$', which allows '&' to be nested in '$'.
--
-- >>> 5 & (+1) & show
-- "6"
--
-- @since 4.8.0.0
(&) :: a -> (a -> b) -> b
x & f = f x
-- | 'applyWhen' applies a function to a value if a condition is true,
-- otherwise, it returns the value unchanged.
--
-- It is equivalent to @'flip' ('Data.Bool.bool' 'id')@.
--
-- Algebraic properties:
--
-- * @applyWhen 'True' = 'id'@
--
-- * @applyWhen 'False' f = 'id'@
--
-- @since 4.18.0.0
applyWhen :: Bool -> (a -> a) -> a -> a
applyWhen True f x = f x
applyWhen False _ x = x
-- Proofs:
--
-- flip bool id = \q f -> bool id f q
-- = \f q -> case q of
-- True -> f = \x -> f x
-- False -> id = \x -> x ∎
--
-- applyWhen True = \f x -> f x
-- = \f -> \x -> f x = \f -> f = id ∎
--
-- applyWhen False f = \x -> x = id ∎
-- $setup
-- >>> import Prelude
|
