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