1 /*! 2 @file 3 Forward declares `boost::hana::Searchable`. 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_SEARCHABLE_HPP 11 #define BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP 12 13 #include <boost/hana/config.hpp> 14 15 16 BOOST_HANA_NAMESPACE_BEGIN 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 BOOST_HANA_NAMESPACE_END 142 143 #endif // !BOOST_HANA_FWD_CONCEPT_SEARCHABLE_HPP 144