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
|
/*!
@file
Forward declares `boost::hana::Foldable`.
@copyright Louis Dionne 2013-2016
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
*/
#ifndef BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP
#define BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP
#include <boost/hana/config.hpp>
BOOST_HANA_NAMESPACE_BEGIN
//! @ingroup group-concepts
//! @defgroup group-Foldable Foldable
//! The `Foldable` concept represents data structures that can be reduced
//! to a single value.
//!
//! Generally speaking, folding refers to the concept of summarizing a
//! complex structure as a single value, by successively applying a
//! binary operation which reduces two elements of the structure to a
//! single value. Folds come in many flavors; left folds, right folds,
//! folds with and without an initial reduction state, and their monadic
//! variants. This concept is able to express all of these fold variants.
//!
//! Another way of seeing `Foldable` is as data structures supporting
//! internal iteration with the ability to accumulate a result. By
//! internal iteration, we mean that the _loop control_ is in the hand
//! of the structure, not the caller. Hence, it is the structure who
//! decides when the iteration stops, which is normally when the whole
//! structure has been consumed. Since C++ is an eager language, this
//! requires `Foldable` structures to be finite, or otherwise one would
//! need to loop indefinitely to consume the whole structure.
//!
//! @note
//! While the fact that `Foldable` only works for finite structures may
//! seem overly restrictive in comparison to the Haskell definition of
//! `Foldable`, a finer grained separation of the concepts should
//! mitigate the issue. For iterating over possibly infinite data
//! structures, see the `Iterable` concept. For searching a possibly
//! infinite data structure, see the `Searchable` concept.
//!
//!
//! Minimal complete definition
//! ---------------------------
//! `fold_left` or `unpack`
//!
//! However, please note that a minimal complete definition provided
//! through `unpack` will be much more compile-time efficient than one
//! provided through `fold_left`.
//!
//!
//! Concrete models
//! ---------------
//! `hana::map`, `hana::optional`, `hana::pair`, `hana::set`,
//! `hana::range`, `hana::tuple`
//!
//!
//! @anchor Foldable-lin
//! The linearization of a `Foldable`
//! ---------------------------------
//! Intuitively, for a `Foldable` structure `xs`, the _linearization_ of
//! `xs` is the sequence of all the elements in `xs` as if they had been
//! put in a list:
//! @code
//! linearization(xs) = [x1, x2, ..., xn]
//! @endcode
//!
//! Note that it is always possible to produce such a linearization
//! for a finite `Foldable` by setting
//! @code
//! linearization(xs) = fold_left(xs, [], flip(prepend))
//! @endcode
//! for an appropriate definition of `[]` and `prepend`. The notion of
//! linearization is useful for expressing various properties of
//! `Foldable` structures, and is used across the documentation. Also
//! note that `Iterable`s define an [extended version](@ref Iterable-lin)
//! of this allowing for infinite structures.
//!
//!
//! Compile-time Foldables
//! ----------------------
//! A compile-time `Foldable` is a `Foldable` whose total length is known
//! at compile-time. In other words, it is a `Foldable` whose `length`
//! method returns a `Constant` of an unsigned integral type. When
//! folding a compile-time `Foldable`, the folding can be unrolled,
//! because the final number of steps of the algorithm is known at
//! compile-time.
//!
//! Additionally, the `unpack` method is only available to compile-time
//! `Foldable`s. This is because the return _type_ of `unpack` depends
//! on the number of objects in the structure. Being able to resolve
//! `unpack`'s return type at compile-time hence requires the length of
//! the structure to be known at compile-time too.
//!
//! __In the current version of the library, only compile-time `Foldable`s
//! are supported.__ While it would be possible in theory to support
//! runtime `Foldable`s too, doing so efficiently requires more research.
//!
//!
//! Provided conversion to `Sequence`s
//! ----------------------------------
//! Given a tag `S` which is a `Sequence`, an object whose tag is a model
//! of the `Foldable` concept can be converted to an object of tag `S`.
//! In other words, a `Foldable` can be converted to a `Sequence` `S`, by
//! simply taking the linearization of the `Foldable` and creating the
//! sequence with that. More specifically, given a `Foldable` `xs` with a
//! linearization of `[x1, ..., xn]` and a `Sequence` tag `S`, `to<S>(xs)`
//! is equivalent to `make<S>(x1, ..., xn)`.
//! @include example/foldable/to.cpp
//!
//!
//! Free model for builtin arrays
//! -----------------------------
//! Builtin arrays whose size is known can be folded as-if they were
//! homogeneous tuples. However, note that builtin arrays can't be
//! made more than `Foldable` (e.g. `Iterable`) because they can't
//! be empty and they also can't be returned from functions.
//!
//!
//! @anchor monadic-folds
//! Primer on monadic folds
//! -----------------------
//! A monadic fold is a fold in which subsequent calls to the binary
//! function are chained with the monadic `chain` operator of the
//! corresponding Monad. This allows a structure to be folded in a
//! custom monadic context. For example, performing a monadic fold with
//! the `hana::optional` monad would require the binary function to return
//! the result as a `hana::optional`, and the fold would abort and return
//! `nothing` whenever one of the accumulation step would fail (i.e.
//! return `nothing`). If, however, all the reduction steps succeed,
//! then `just` the result would be returned. Different monads will of
//! course result in different effects.
template <typename T>
struct Foldable;
BOOST_HANA_NAMESPACE_END
#endif // !BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP
|
