1 /*!
2 @file
3 Forward declares `boost::hana::Foldable`.
4 
5 @copyright Louis Dionne 2013-2017
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 namespace 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