extensional.cppm File Reference

ExtensionalSet — the canonical small-finite extensional carrier, with std::set / std::unordered_set round-trips. More...

#include <algorithm>
#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <ranges>
#include <set>
#include <type_traits>
#include <unordered_set>
#include <utility>
import dedekind.sets:computability;
import dedekind.category;

Include dependency graph for extensional.cppm:

Classes
struct	dedekind::sets::ExtensionalSet< T, L, Hash, Equal >
struct	dedekind::sets::detail::insert_into
	The step of the folds below: insert one element into the container accumulated so far, and hand it on (Rule 3: a fold, not a loop). The element is taken by value and moved in, so a transformed result is moved, not copied (a move-only one included). More...
struct	dedekind::sets::detail::decided< Chi >
	A classifier read as a decided truth value: its answer converted to bool as if would convert it, so a classifier valued in an explicit truth type (Truth<Boole>) is admitted. Applied as a const value. More...

Namespaces
namespace	dedekind::sets

Concepts
concept	dedekind::sets::StdSetLike
concept	dedekind::sets::detail::StdSetLikeOf

Functions
template<typename StdSetLike, typename T, typename L, typename Hash, typename Equal> requires detail::StdSetLikeOf<StdSetLike, T>
constexpr auto	dedekind::sets::to_std (const dedekind::sets::ExtensionalSet< T, L, Hash, Equal > &source) -> StdSetLike
template<typename StdSetLike, typename ExtSet>
constexpr auto	dedekind::sets::to_std (const ExtSet &) -> StdSetLike
template<typename T, typename Alloc> requires dedekind::category::IsHashFunction<std::hash<T>, T> && std::regular<T>
constexpr auto	dedekind::sets::from_std (const std::set< T, std::less< T >, Alloc > &source) -> dedekind::sets::ExtensionalSet< T >
template<typename T, typename Alloc> requires (!dedekind::category::IsHashFunction<std::hash<T>, T> || !std::regular<T>)
constexpr auto	dedekind::sets::from_std (const std::set< T, std::less< T >, Alloc > &) -> dedekind::sets::ExtensionalSet< T >
template<typename T, typename Compare, typename Alloc> requires (!std::same_as<Compare, std::less<T>>)
constexpr auto	dedekind::sets::from_std (const std::set< T, Compare, Alloc > &) -> dedekind::sets::ExtensionalSet< T >
template<typename T, typename Hash, typename Equal, typename Alloc>
constexpr auto	dedekind::sets::from_std (const std::unordered_set< T, Hash, Equal, Alloc > &source) -> dedekind::sets::ExtensionalSet< T, dedekind::category::Boole, Hash, Equal >
template<typename StdSetLike> requires dedekind::sets::StdSetLike<StdSetLike>
constexpr auto	dedekind::sets::from_std (const StdSetLike &) -> dedekind::sets::ExtensionalSet< typename StdSetLike::value_type >
template<typename ExtSet, typename StdSetLike>
constexpr auto	dedekind::sets::from_std (const StdSetLike &) -> ExtSet
template<typename U, typename Chi> requires std::ranges::input_range<const U> && std::totally_ordered<std::ranges::range_value_t<const U>> && std::invocable<const Chi&, std::ranges::range_reference_t<const U>> && std::constructible_from< bool, std::invoke_result_t< const Chi&, std::ranges::range_reference_t<const U>>>
constexpr auto	dedekind::sets::ext (const U &universe, Chi chi)
	μ: Int ⇀ Ext, the partial retraction of ambient_set.
template<typename T, typename Hash, typename Equal, typename Alloc, typename F> requires std::invocable<F&, const T&>
constexpr auto	dedekind::sets::image (F f, const std::unordered_set< T, Hash, Equal, Alloc > &s)
	image(f, std::unordered_set<T, Hash, Equal, Alloc>). An rvalue source binds here too: the image is a new container either way.
template<typename T, typename Compare, typename Alloc, typename F> requires std::invocable<F&, const T&>
constexpr auto	dedekind::sets::image (F f, const std::set< T, Compare, Alloc > &s)
	image(f, std::set<T, Compare, Alloc>).
template<typename T, typename Hash, typename Equal, typename Alloc, typename P> requires std::predicate<const P&, const T&>
constexpr auto	dedekind::sets::filter (P p, const std::unordered_set< T, Hash, Equal, Alloc > &s)
	filter(p, std::unordered_set<T, Hash, Equal, Alloc>).
template<typename T, typename Compare, typename Alloc, typename P> requires std::predicate<const P&, const T&>
constexpr auto	dedekind::sets::filter (P p, const std::set< T, Compare, Alloc > &s)
	filter(p, std::set<T, Compare, Alloc>).

Variables
template<typename...>
constexpr bool	dedekind::sets::detail::always_false_v = false

Detailed Description

ExtensionalSet — the canonical small-finite extensional carrier, with std::set / std::unordered_set round-trips.

@partition :extensional

In any computable representation an extensional set (one defined by listing its elements rather than by predicate) is necessarily finite, so the Finite qualifier is dropped from the carrier name; the finiteness and countability propositions are kept as static_assert breadcrumbs against IsExtensional / IsFinite / IsCountable (#598 acceptance).

The std-container bridges (from_std / to_std) live in this partition rather than in a separate :interop sister, since they are constructors / accessors of ExtensionalSet — there is no "interop" surface independent of the carrier they materialise.

Copyright

2026 The Dedekind Authors Licensed under the Apache License, Version 2.0.

Note

"At the heart of generic programming is a single, simple idea: program over the most abstract type that supports the operations the algorithm needs." [Trans: original is English; the gloss is that the carrier's std-container bridges should ask only for the minimal interface the algorithm uses, not commit either side to the other's representational choices.] — Alexander A. Stepanov & Daniel E. Rose, From Mathematics to Generic Programming (Addison-Wesley, 2014), §1. Stepanov designed the STL on this principle; the bridges honour it by translating across the rule-vs-bucket boundary (Dedekind predicate-set ↔ std container) without forcing either side into the other's vocabulary.