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