1/*!
2@file
3Forward declares `boost::hana::Foldable`.
4
5Copyright Louis Dionne 2013-2022
6Distributed 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
16namespace boost { namespace hana {
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}} // end namespace boost::hana
140
141#endif // !BOOST_HANA_FWD_CONCEPT_FOLDABLE_HPP
142

source code of boost/libs/hana/include/boost/hana/fwd/concept/foldable.hpp