1/*!
2@file
3Forward declares `boost::hana::Searchable`.
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_SEARCHABLE_HPP
11#define BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP
12
13#include <boost/hana/config.hpp>
14
15
16namespace boost { namespace hana {
17 //! @ingroup group-concepts
18 //! @defgroup group-Searchable Searchable
19 //! The `Searchable` concept represents structures that can be searched.
20 //!
21 //! Intuitively, a `Searchable` is any structure, finite or infinite,
22 //! containing elements that can be searched using a predicate. Sometimes,
23 //! `Searchable`s will associate keys to values; one can search for a key
24 //! with a predicate, and the value associated to it is returned. This
25 //! gives rise to map-like data structures. Other times, the elements of
26 //! the structure that are searched (i.e. those to which the predicate is
27 //! applied) are the same that are returned, which gives rise to set-like
28 //! data structures. In general, we will refer to the _keys_ of a
29 //! `Searchable` structure as those elements that are used for searching,
30 //! and to the _values_ of a `Searchable` as those elements that are
31 //! returned when a search is successful. As was explained, there is no
32 //! requirement that both notions differ, and it is often useful to have
33 //! keys and values coincide (think about `std::set`).
34 //!
35 //! Some methods like `any_of`, `all_of` and `none_of` allow simple queries
36 //! to be performed on the keys of the structure, while other methods like
37 //! `find` and `find_if` make it possible to find the value associated
38 //! to a key. The most specific method should always be used if one
39 //! cares about performance, because it is usually the case that heavy
40 //! optimizations can be performed in more specific methods. For example,
41 //! an associative data structure implemented as a hash table will be much
42 //! faster to access using `find` than `find_if`, because in the second
43 //! case it will have to do a linear search through all the entries.
44 //! Similarly, using `contains` will likely be much faster than `any_of`
45 //! with an equivalent predicate.
46 //!
47 //! > __Insight__\n
48 //! > In a lazy evaluation context, any `Foldable` can also become a model
49 //! > of `Searchable` because we can search lazily through the structure
50 //! > with `fold_right`. However, in the context of C++, some `Searchable`s
51 //! > can not be folded; think for example of an infinite set.
52 //!
53 //!
54 //! Minimal complete definition
55 //! ---------------------------
56 //! `find_if` and `any_of`
57 //!
58 //! When `find_if` and `any_of` are provided, the other functions are
59 //! implemented according to the laws explained below.
60 //!
61 //! @note
62 //! We could implement `any_of(xs, pred)` by checking whether
63 //! `find_if(xs, pred)` is an empty `optional` or not, and then reduce
64 //! the minimal complete definition to `find_if`. However, this is not
65 //! done because that implementation requires the predicate of `any_of`
66 //! to return a compile-time `Logical`, which is more restrictive than
67 //! what we have right now.
68 //!
69 //!
70 //! Laws
71 //! ----
72 //! In order for the semantics of the methods to be consistent, some
73 //! properties must be satisfied by any model of the `Searchable` concept.
74 //! Rigorously, for any `Searchable`s `xs` and `ys` and any predicate `p`,
75 //! the following laws should be satisfied:
76 //! @code
77 //! any_of(xs, p) <=> !all_of(xs, negated p)
78 //! <=> !none_of(xs, p)
79 //!
80 //! contains(xs, x) <=> any_of(xs, equal.to(x))
81 //!
82 //! find(xs, x) == find_if(xs, equal.to(x))
83 //! find_if(xs, always(false_)) == nothing
84 //!
85 //! is_subset(xs, ys) <=> all_of(xs, [](auto x) { return contains(ys, x); })
86 //! is_disjoint(xs, ys) <=> none_of(xs, [](auto x) { return contains(ys, x); })
87 //! @endcode
88 //!
89 //! Additionally, if all the keys of the `Searchable` are `Logical`s,
90 //! the following laws should be satisfied:
91 //! @code
92 //! any(xs) <=> any_of(xs, id)
93 //! all(xs) <=> all_of(xs, id)
94 //! none(xs) <=> none_of(xs, id)
95 //! @endcode
96 //!
97 //!
98 //! Concrete models
99 //! ---------------
100 //! `hana::map`, `hana::optional`, `hana::range`, `hana::set`,
101 //! `hana::string`, `hana::tuple`
102 //!
103 //!
104 //! Free model for builtin arrays
105 //! -----------------------------
106 //! Builtin arrays whose size is known can be searched as-if they were
107 //! homogeneous tuples. However, since arrays can only hold objects of
108 //! a single type and the predicate to `find_if` must return a compile-time
109 //! `Logical`, the `find_if` method is fairly useless. For similar reasons,
110 //! the `find` method is also fairly useless. This model is provided mainly
111 //! because of the `any_of` method & friends, which are both useful and
112 //! compile-time efficient.
113 //!
114 //!
115 //! Structure preserving functions
116 //! ------------------------------
117 //! Given two `Searchables` `S1` and `S2`, a function
118 //! @f$ f : S_1(X) \to S_2(X) @f$ is said to preserve the `Searchable`
119 //! structure if for all `xs` of data type `S1(X)` and predicates
120 //! @f$ \mathtt{pred} : X \to Bool @f$ (for a `Logical` `Bool`),
121 //! @code
122 //! any_of(xs, pred) if and only if any_of(f(xs), pred)
123 //! find_if(xs, pred) == find_if(f(xs), pred)
124 //! @endcode
125 //!
126 //! This is really just a generalization of the following, more intuitive
127 //! requirements. For all `xs` of data type `S1(X)` and `x` of data type
128 //! `X`,
129 //! @code
130 //! x ^in^ xs if and only if x ^in^ f(xs)
131 //! find(xs, x) == find(f(xs), x)
132 //! @endcode
133 //!
134 //! These requirements can be understood as saying that `f` does not
135 //! change the content of `xs`, although it may reorder elements.
136 //! As usual, such a structure-preserving transformation is said to
137 //! be an embedding if it is also injective, i.e. if it is a lossless
138 //! transformation.
139 template <typename S>
140 struct Searchable;
141}} // end namespace boost::hana
142
143#endif // !BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP
144

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