]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Foldable`. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Foldable Foldable | |
19 | //! The `Foldable` concept represents data structures that can be reduced | |
20 | //! to a single value. | |
21 | //! | |
22 | //! Generally speaking, folding refers to the concept of summarizing a | |
23 | //! complex structure as a single value, by successively applying a | |
24 | //! binary operation which reduces two elements of the structure to a | |
25 | //! single value. Folds come in many flavors; left folds, right folds, | |
26 | //! folds with and without an initial reduction state, and their monadic | |
27 | //! variants. This concept is able to express all of these fold variants. | |
28 | //! | |
29 | //! Another way of seeing `Foldable` is as data structures supporting | |
30 | //! internal iteration with the ability to accumulate a result. By | |
31 | //! internal iteration, we mean that the _loop control_ is in the hand | |
32 | //! of the structure, not the caller. Hence, it is the structure who | |
33 | //! decides when the iteration stops, which is normally when the whole | |
34 | //! structure has been consumed. Since C++ is an eager language, this | |
35 | //! requires `Foldable` structures to be finite, or otherwise one would | |
36 | //! need to loop indefinitely to consume the whole structure. | |
37 | //! | |
38 | //! @note | |
39 | //! While the fact that `Foldable` only works for finite structures may | |
40 | //! seem overly restrictive in comparison to the Haskell definition of | |
41 | //! `Foldable`, a finer grained separation of the concepts should | |
42 | //! mitigate the issue. For iterating over possibly infinite data | |
43 | //! structures, see the `Iterable` concept. For searching a possibly | |
44 | //! infinite data structure, see the `Searchable` concept. | |
45 | //! | |
46 | //! | |
47 | //! Minimal complete definition | |
48 | //! --------------------------- | |
49 | //! `fold_left` or `unpack` | |
50 | //! | |
51 | //! However, please note that a minimal complete definition provided | |
52 | //! through `unpack` will be much more compile-time efficient than one | |
53 | //! provided through `fold_left`. | |
54 | //! | |
55 | //! | |
56 | //! Concrete models | |
57 | //! --------------- | |
58 | //! `hana::map`, `hana::optional`, `hana::pair`, `hana::set`, | |
59 | //! `hana::range`, `hana::tuple` | |
60 | //! | |
61 | //! | |
62 | //! @anchor Foldable-lin | |
63 | //! The linearization of a `Foldable` | |
64 | //! --------------------------------- | |
65 | //! Intuitively, for a `Foldable` structure `xs`, the _linearization_ of | |
66 | //! `xs` is the sequence of all the elements in `xs` as if they had been | |
67 | //! put in a list: | |
68 | //! @code | |
69 | //! linearization(xs) = [x1, x2, ..., xn] | |
70 | //! @endcode | |
71 | //! | |
72 | //! Note that it is always possible to produce such a linearization | |
73 | //! for a finite `Foldable` by setting | |
74 | //! @code | |
75 | //! linearization(xs) = fold_left(xs, [], flip(prepend)) | |
76 | //! @endcode | |
77 | //! for an appropriate definition of `[]` and `prepend`. The notion of | |
78 | //! linearization is useful for expressing various properties of | |
79 | //! `Foldable` structures, and is used across the documentation. Also | |
80 | //! note that `Iterable`s define an [extended version](@ref Iterable-lin) | |
81 | //! of this allowing for infinite structures. | |
82 | //! | |
83 | //! | |
84 | //! Compile-time Foldables | |
85 | //! ---------------------- | |
86 | //! A compile-time `Foldable` is a `Foldable` whose total length is known | |
87 | //! at compile-time. In other words, it is a `Foldable` whose `length` | |
88 | //! method returns a `Constant` of an unsigned integral type. When | |
89 | //! folding a compile-time `Foldable`, the folding can be unrolled, | |
90 | //! because the final number of steps of the algorithm is known at | |
91 | //! compile-time. | |
92 | //! | |
93 | //! Additionally, the `unpack` method is only available to compile-time | |
94 | //! `Foldable`s. This is because the return _type_ of `unpack` depends | |
95 | //! on the number of objects in the structure. Being able to resolve | |
96 | //! `unpack`'s return type at compile-time hence requires the length of | |
97 | //! the structure to be known at compile-time too. | |
98 | //! | |
99 | //! __In the current version of the library, only compile-time `Foldable`s | |
100 | //! are supported.__ While it would be possible in theory to support | |
101 | //! runtime `Foldable`s too, doing so efficiently requires more research. | |
102 | //! | |
103 | //! | |
104 | //! Provided conversion to `Sequence`s | |
105 | //! ---------------------------------- | |
106 | //! Given a tag `S` which is a `Sequence`, an object whose tag is a model | |
107 | //! of the `Foldable` concept can be converted to an object of tag `S`. | |
108 | //! In other words, a `Foldable` can be converted to a `Sequence` `S`, by | |
109 | //! simply taking the linearization of the `Foldable` and creating the | |
110 | //! sequence with that. More specifically, given a `Foldable` `xs` with a | |
111 | //! linearization of `[x1, ..., xn]` and a `Sequence` tag `S`, `to<S>(xs)` | |
112 | //! is equivalent to `make<S>(x1, ..., xn)`. | |
113 | //! @include example/foldable/to.cpp | |
114 | //! | |
115 | //! | |
116 | //! Free model for builtin arrays | |
117 | //! ----------------------------- | |
118 | //! Builtin arrays whose size is known can be folded as-if they were | |
119 | //! homogeneous tuples. However, note that builtin arrays can't be | |
120 | //! made more than `Foldable` (e.g. `Iterable`) because they can't | |
121 | //! be empty and they also can't be returned from functions. | |
122 | //! | |
123 | //! | |
124 | //! @anchor monadic-folds | |
125 | //! Primer on monadic folds | |
126 | //! ----------------------- | |
127 | //! A monadic fold is a fold in which subsequent calls to the binary | |
128 | //! function are chained with the monadic `chain` operator of the | |
129 | //! corresponding Monad. This allows a structure to be folded in a | |
130 | //! custom monadic context. For example, performing a monadic fold with | |
131 | //! the `hana::optional` monad would require the binary function to return | |
132 | //! the result as a `hana::optional`, and the fold would abort and return | |
133 | //! `nothing` whenever one of the accumulation step would fail (i.e. | |
134 | //! return `nothing`). If, however, all the reduction steps succeed, | |
135 | //! then `just` the result would be returned. Different monads will of | |
136 | //! course result in different effects. | |
137 | template <typename T> | |
138 | struct Foldable; | |
139 | BOOST_HANA_NAMESPACE_END | |
140 | ||
141 | #endif // !BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP |