/
lazy.h
408 lines (370 loc) · 10.4 KB
/
lazy.h
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
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
/*
* Copyright (c) 2013 Björn Aili
*
* This software is provided 'as-is', without any express or implied
* warranty. In no event will the authors be held liable for any damages
* arising from the use of this software.
*
* Permission is granted to anyone to use this software for any purpose,
* including commercial applications, and to alter it and redistribute it
* freely, subject to the following restrictions:
*
* 1. The origin of this software must not be misrepresented; you must not
* claim that you wrote the original software. If you use this software
* in a product, an acknowledgment in the product documentation would be
* appreciated but is not required.
*
* 2. Altered source versions must be plainly marked as such, and must not be
* misrepresented as being the original software.
*
* 3. This notice may not be removed or altered from any source
* distribution.
*/
#ifndef FTL_LAZY_H
#define FTL_LAZY_H
#include <memory>
#include "prelude.h"
#include "concepts/monoid.h"
#include "either.h"
namespace ftl {
/**
* \defgroup lazy Lazy
*
* The lazy data type and its concept instances.
*
* \code
* #include <ftl/lazy.h>
* \endcode
*
* \par Dependencies
* - \ref prelude
* - \ref monoid
* - \ref either
*/
/**
* Enumeration of the states a lazy computation can be in.
*
* Mainly used in combination with ftl::lazy::valueStatus().
*
* \ingroup lazy
*/
enum class value_status {
/// The computation still has not been performed
deferred,
/// The value is computed and ready
ready
};
/**
* The lazy data type.
*
* Wraps a value of type `T`, causing its evaluation to be deferred until
* such a time as it is required.
*
* To reduce the number of times a particular computation is made, copies
* (as created by e.g. the copy constructor) of a particular `lazy` all
* refer to a shared object representing either the computed value, or the
* computation that will yield the value. Hence, the computation will only
* be made _once_ for every set of copies ultimately derived from the same
* source.
*
* If no instance of a particular computation ever forces it, then it simply
* won't be evaluated at all.
*
* As a convenience, there is a specialisation of `lazy` for `bool` that
* allows contextual conversions of `lazy<bool>` to `bool`, allowing
* expressions such as `if(lazyBool) doSomething();`. This will force
* evaluation.
*
* \note Lazy values are immutable. Bypassing this with some creative
* casting may result in undefined behaviour.
*
* \par Concepts
* - \ref copycons
* - \ref movecons
* - \ref assignable (note that assigning to a `lazy` does not change or
* force the underlying computation, it merely changes _what_
* computation that particular `lazy` encapsulates.
* - \ref deref to `T` (_forces_ evaluation).
* - \ref functor
* - \ref applicative
* - \ref monad
* - \ref eq, if `T` is EqualityComparable.
* - \ref orderable, if `T` is Orderable.
* - \ref monoid, if `T` is a Monoid.
*
* \ingroup lazy
*/
template<typename T>
class lazy {
public:
lazy() = delete;
lazy(const lazy&) = default;
lazy(lazy&&) = default;
~lazy() = default;
/**
* Construct from a no-argument function object.
*
* In essence, whenever the value is first _forced_, the function
* object will be invoked to compute it. Any subsequent calls to methods
* that would normally force evaluation will simply use the now computed
* value.
*/
explicit lazy(const function<T()>& f)
: val(new either<function<T()>,T>(make_left<T>(f)))
{}
/**
* Get a reference to the value.
*
* This method forces evaluation.
*/
const T& operator*() const {
force();
return *get<1>(*val);
}
/**
* Access members of the lazy value.
*
* This method forces evaluation.
*/
const T* operator->() const {
if(val->template is<Right<T>>())
return std::addressof(*get<1>(*val));
force();
return std::addressof(*get<1>(*val));
}
lazy& operator= (const lazy&) = default;
lazy& operator= (lazy&&) = default;
/**
* Check the state of the deferred computation.
*
* \return value_status::deferred if computation has not yet been run,
* and value_status::ready if it has.
*/
value_status status() const {
if(val->template is<Right<T>>())
return value_status::ready;
return value_status::deferred;
}
private:
void force() const {
if(val->template is<Right<T>>())
return;
*val = make_right<function<T()>>((*get<0>(*val))());
}
mutable std::shared_ptr<either<function<T()>,T>> val;
};
// Bool specialisation to allow contextual conversion
template<>
class lazy<bool> {
public:
lazy() = delete;
lazy(const lazy&) = default;
lazy(lazy&&) = default;
~lazy() = default;
explicit lazy(const function<bool()>& f)
: val(new either<function<bool()>,bool>(make_left<bool>(f)))
{}
const bool& operator*() const {
force();
return *get<Right<bool>>(*val);
}
lazy& operator= (const lazy&) = default;
lazy& operator= (lazy&&) = default;
explicit operator bool() {
force();
return *get<Right<bool>>(*val);
}
value_status status() const {
if(val->is<Right<bool>>())
return value_status::ready;
return value_status::deferred;
}
private:
void force() const {
if(val->is<Right<bool>>())
return;
*val = make_right<function<bool()>>((*get<0>(*val))());
}
mutable std::shared_ptr<either<function<bool()>,bool>> val;
};
/**
* Create a lazy computation from an arbitrary function.
*
* Currently, all parameters are _copied_ when `defer` is called. If you
* want to call by reference on some parameter, you should use `std::cref`
* (the use of `std::ref` is not encouraged, because it allows mutation
* of the parameter and all lazy computations are assumed to be pure, in
* the sense that they should have no side effects, nor contain any state).
*
* \note `f` is assumed to be of unary or greater arity. If a deferred zero
* argument computation is desired, use lazy's constructor directly.
*
* \ingroup lazy
*/
template<
typename F,
typename...Args,
typename T = result_of<F(Args...)>
>
lazy<T> defer(F f, Args&&...args) {
// TODO: C++14: _move_ tuple of args into lambda
// TODO: Make this work with zero-argument fs
auto t = std::make_tuple(std::forward<Args>(args)...);
return lazy<T>{[f,t]() {
return tuple_apply(f, t);
}};
}
/**
* Equality comparison.
*
* Does not evaluate `l1` or `l2` until the returned computation is
* itself evaluated.
*
* \tparam T must have an `operator==`.
*
* \ingroup lazy
*/
template<typename T>
lazy<bool> operator==(lazy<T> l1, lazy<T> l2) {
return lazy<bool>{[l1,l2]() {
return *l1 == *l2;
}};
}
/**
* Not equal comparison.
*
* Does not evaluate `l1` or `l2` until the returned computation is
* itself evaluated.
*
* \tparam T must have an `operator!=`.
*
* \ingroup lazy
*/
template<typename T>
lazy<bool> operator!=(lazy<T> l1, lazy<T> l2) {
return lazy<bool>{[l1,l2]() {
return *l1 != *l2;
}};
}
/**
* Less than comparison
*
* Does not evaluate `lhs` or `rhs` until the returned computation is
* itself evaluated.
*
* \tparam T must have an `operator<`.
*
* \ingroup lazy
*/
template<typename T>
lazy<bool> operator< (lazy<T> lhs, lazy<T> rhs) {
return lazy<bool>{[lhs,rhs]() {
return *lhs < *rhs;
}};
}
/**
* Greater than comparison
*
* Does not evaluate `lhs` or `rhs` until the returned computation is
* itself evaluated.
*
* \tparam T must have an `operator>`.
*
* \ingroup lazy
*/
template<typename T>
lazy<bool> operator> (lazy<T> lhs, lazy<T> rhs) {
return lazy<bool>{[lhs,rhs]() {
return *lhs > *rhs;
}};
}
/**
* Monad instance for lazy values.
*
* Allows users to build "thunks" of computations, all left uncomputed until
* forced.
*
* \ingroup lazy
*/
template<typename T>
struct monad<lazy<T>>
: deriving_join<in_terms_of_bind<lazy<T>>>
, deriving_apply<in_terms_of_bind<lazy<T>>> {
/**
* Create a computation that computes `t`
*
* Sounds a bit silly—we already know `t` after all—but
* there are situations when it can be useful (e.g. algorithms
* generalised over any monad).
*/
static lazy<T> pure(T t) {
return lazy<T>{[t](){ return t; }};
}
// TODO: C++14: Add a pure that captures Ts by move
/**
* Map a function to the deferred value.
*
* As expected, this does not actually compute the deferred value
* in `l`. Instead, we simply defer both the invocation of `f` and
* the computation of `l` until someone forces the _returned_ lazy
* copmutation (though technically, `l` could be forced by another,
* independant computation ahead of that).
*/
template<typename F, typename U = result_of<F(T)>>
static lazy<U> map(F f, lazy<T> l) {
return lazy<U>{function<U()>{[f,l]() { return f(*l); }}};
}
/**
* Sequences two lazy computations.
*
* As with functor<lazy<T>>::map, the whole bind is deferred until
* the returned computation is forced.
*
* Note that, again as with `map`, the lazy computation `l` could be
* forced ahead of time by unrelated code elsewhere. This is due to the
* shared nature of lazy values (copies always refer to the same
* internal object as the original).
*/
template<
typename F,
typename U = Value_type<result_of<F(T)>>
>
static lazy<U> bind(lazy<T> l, F f) {
return lazy<U>{[f,l]() {
return *(f(*l));
}};
}
static constexpr bool instance = true;
};
/**
* Monoid instance of lazy computations.
*
* \tparam T must be a monoid to begin with.
*
* This instance is exactly equivalent of `T`'s monoid instance, except
* that the computations of `monoid<T>::id()` and `monoid<T>::append()` are
* of course deferred until forced.
*
* \ingroup lazy
*/
template<typename T>
struct monoid<lazy<T>> {
/**
* Lazily "computes" monoid<T>::id()
*/
static lazy<T> id() {
return lazy<T>{monoid<T>::id};
}
/**
* Lazily computes monoid<T>::append(*l1, *l2).
*
* Note that neither `l1` nor `l2` are forced by invoking this function.
* They are, of course, forced when the result of this computation is.
*/
static lazy<T> append(lazy<T> l1, lazy<T> l2) {
return lazy<T>([l1,l2](){ return monoid<T>::append(*l1, *l2); });
}
static constexpr bool instance = monoid<T>::instance;
};
}
#endif