-
Notifications
You must be signed in to change notification settings - Fork 437
/
AndThen.kt
258 lines (236 loc) · 7.64 KB
/
AndThen.kt
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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
package arrow.core
/**
* [AndThen] wraps a function of shape `(A) -> B` and can be used to do function composition.
* It's similar to [arrow.core.andThen] and [arrow.core.compose] and can be used to build stack safe
* data structures that make use of lambdas. Usage is typically used for signature such as `A -> Kind<F, A>` where
* `F` has a [arrow.typeclasses.Monad] instance i.e. [StateT.flatMap].
*
* As you can see the usage of [AndThen] is the same as `[arrow.core.andThen] except we start our computation by
* wrapping our function in [AndThen].
*
* ```kotlin:ank:playground
* import arrow.core.andThen
* import arrow.core.AndThen
*
* fun main(args: Array<String>) {
* //sampleStart
* val f = (0..10000).toList()
* .fold({ x: Int -> x + 1 }) { acc, _ ->
* acc.andThen { it + 1 }
* }
*
* val f2 = (0..10000).toList()
* .fold(AndThen { x: Int -> x + 1 }) { acc, _ ->
* acc.andThen { it + 1 }
* }
* //sampleEnd
* println("f(0) = ${f(0)}, f2(0) = ${f2(0)}")
* }
* ```
*
*/
@Deprecated(
"AndThen is becoming an internal data type that automatically tries to make andThen stack safe",
level = DeprecationLevel.WARNING
)
sealed class AndThen<A, B> : (A) -> B {
private data class Single<A, B>(val f: (A) -> B, val index: Int) : AndThen<A, B>()
private data class Join<A, B>(val fa: AndThen<A, AndThen<A, B>>) : AndThen<A, B>() {
override fun toString(): String = "AndThen.Join(...)"
}
private data class Concat<A, E, B>(val left: AndThen<A, E>, val right: AndThen<E, B>) : AndThen<A, B>() {
override fun toString(): String = "AndThen.Concat(...)"
}
/**
* Compose a function to be invoked after the current function is invoked.
*
* ```kotlin:ank:playground
* import arrow.core.AndThen
*
* fun main(args: Array<String>) {
* //sampleStart
* val f = (0..10000).toList().fold(AndThen { i: Int -> i + 1 }) { acc, _ ->
* acc.andThen { it + 1 }
* }
*
* val result = f(0)
* //sampleEnd
* println("result = $result")
* }
* ```
*
* @param g function to apply on the result of this function.
* @return a composed [AndThen] function that first applies this function to its input,
* and then applies [g] to the result.
*/
fun <X> andThen(g: (B) -> X): AndThen<A, X> =
when (this) {
// Fusing calls up to a certain threshold
is Single ->
if (index != maxStackDepthSize) Single({ a: A -> g(this(a)) }, index + 1)
else andThenF(AndThen(g))
else -> andThenF(AndThen(g))
}
/**
* Compose a function to be invoked before the current function is invoked.
*
* ```kotlin:ank:playground
* import arrow.core.AndThen
*
* fun main(args: Array<String>) {
* //sampleStart
* val f = (0..10000).fold(AndThen { i: Int -> i + 1 }) { acc, _ ->
* acc.compose { it + 1 }
* }
*
* val result = f(0)
* //sampleEnd
* println("result = $result")
* }
* ```
*
* @param g function to invoke before invoking this function with the result.
* @return a composed [AndThen] function that first applies [g] to its input,
* and then applies this function to the result.
*/
infix fun <C> compose(g: (C) -> A): AndThen<C, B> =
when (this) {
// Fusing calls up to a certain threshold
is Single ->
if (index != maxStackDepthSize) Single({ c: C -> this(g(c)) }, index + 1)
else composeF(AndThen(g))
else -> composeF(AndThen(g))
}
/**
* Alias for [andThen]
*
* @see andThen
*/
fun <C> map(f: (B) -> C): AndThen<A, C> =
andThen(f)
/**
* Alias for [compose]
*
* @see compose
*/
fun <C> contramap(f: (C) -> A): AndThen<C, B> =
this compose f
fun <C> flatMap(f: (B) -> AndThen<A, C>): AndThen<A, C> = Join(this.map(AndThen(f)))
fun <C> ap(ff: AndThen<A, (B) -> C>): AndThen<A, C> =
ff.flatMap { f ->
map(f)
}
/**
* Invoke the `[AndThen]` function
*
* ```kotlin:ank:playground
* import arrow.core.AndThen
*
* fun main(args: Array<String>) {
* //sampleStart
* val f: AndThen<Int, String> = AndThen(Int::toString)
* val result = f.invoke(0)
* //sampleEnd
* println("result = $result")
* }
* ```
*
* @param a value to invoke function with
* @return result of type [B].
*
**/
@Suppress("UNCHECKED_CAST")
override fun invoke(a: A): B = loop(this as AndThen<Any?, Any?>, a, 0)
override fun toString(): String = "AndThen(...)"
companion object {
fun <A, B> just(b: B): AndThen<A, B> =
AndThen { b }
fun <A> id(): AndThen<A, A> =
AndThen(::identity)
/**
* Wraps a function in [AndThen].
*
* ```kotlin:ank:playground
* import arrow.core.AndThen
*
* fun main(args: Array<String>) {
* //sampleStart
* val f = AndThen { x: Int -> x + 1 }
* val result = f(0)
* //sampleEnd
* println("result = $result")
* }
* ```
*
* @param f the function to wrap
* @return wrapped function [f].
*
*/
operator fun <A, B> invoke(f: (A) -> B): AndThen<A, B> = when (f) {
is AndThen<A, B> -> f
else -> Single(f, 0)
}
fun <I, A, B> tailRecM(a: A, f: (A) -> AndThen<I, Either<A, B>>): AndThen<I, B> =
AndThen { t: I -> step(a, t, f) }
private tailrec fun <I, A, B> step(a: A, t: I, fn: (A) -> AndThen<I, Either<A, B>>): B {
val af = fn(a)(t)
return when (af) {
is Either.Right -> af.value
is Either.Left -> step(af.value, t, fn)
}
}
/**
* Establishes the maximum stack depth when fusing `andThen` or `compose` calls.
*
* The default is `128`, from which we substract one as an
* optimization. This default has been reached like this:
*
* - according to official docs, the default stack size on 32-bits
* Windows and Linux was 320 KB, whereas for 64-bits it is 1024 KB
* - according to measurements chaining `Function1` references uses
* approximately 32 bytes of stack space on a 64 bits system;
* this could be lower if "compressed oops" is activated
* - therefore a "map fusion" that goes 128 in stack depth can use
* about 4 KB of stack space
*/
private const val maxStackDepthSize = 127
}
fun <X> andThenF(right: AndThen<B, X>): AndThen<A, X> = Concat(this, right)
fun <X> composeF(right: AndThen<X, A>): AndThen<X, B> = Concat(right, this)
@Suppress("UNCHECKED_CAST")
private tailrec fun loop(self: AndThen<Any?, Any?>, current: Any?, joins: Int): B = when (self) {
is Single -> if (joins == 0) self.f(current) as B else loop(self.f(current) as AndThen<Any?, Any?>, null, joins - 1)
is Join -> loop(
self.fa.andThen { Concat(AndThen<Any?, Any?> { current }, it) },
current,
joins + 1
)
is Concat<*, *, *> -> {
when (val oldLeft = self.left) {
is Single<*, *> -> {
val left = oldLeft as Single<Any?, Any?>
val newSelf = self.right as AndThen<Any?, Any?>
loop(newSelf, left.f(current), joins)
}
is Join<*, *>,
is Concat<*, *, *> -> loop(
rotateAccumulate(self.left as AndThen<Any?, Any?>, self.right as AndThen<Any?, Any?>),
current,
joins
)
}
}
}
@Suppress("UNCHECKED_CAST")
private tailrec fun rotateAccumulate(
left: AndThen<Any?, Any?>,
right: AndThen<Any?, Any?>
): AndThen<Any?, Any?> = when (left) {
is Concat<*, *, *> -> rotateAccumulate(
left.left as AndThen<Any?, Any?>,
(left.right as AndThen<Any?, Any?>).andThenF(right)
)
is Join -> Join(left.fa.andThen { it.andThenF(right) })
is Single<*, *> -> left.andThenF(right)
}
}