comprehension.cppm File Reference

Monad comprehensions over a finite chain: the queries of SQL and LINQ, where, select, order_by and take, and the folds that end them. More...

#include <algorithm>
#include <array>
#include <concepts>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <functional>
#include <limits>
#include <optional>
#include <ranges>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>
#include <version>
import dedekind.category:periodic;

Include dependency graph for comprehension.cppm:

Classes
struct	dedekind::category::detail_comprehension::StepFrom< Op, R >
	A fold step with its accumulator bound, \(a \mapsto \mathit{op}(\mathit{acc}, a)\): the present case of the eliminator. More...
struct	dedekind::category::detail_comprehension::Tally< N >
	One more element into a count. More...
struct	dedekind::category::detail_comprehension::Extended< F >
	A Kleisli arrow into Maybe extended to the elements of a query, \(\kappa(-, f) : \mathit{Maybe}\,A \to \mathit{Maybe}\,B\). More...
struct	dedekind::category::Lifted< Op >
	A fold step lifted through Maybe: Maybe's eliminator with the cases \([\mathit{acc}, \mathit{op}(\mathit{acc}, \cdot)]\), a hole leaving the accumulator as it is. Written once, so the folds that end a query take their plain steps and none cases on a hole. More...
struct	dedekind::category::Where< P >
	where(p), SQL's WHERE: the Kleisli arrow into Maybe that keeps an element where p holds, a hole where it does not. The walk keeps its length, so a filtered chain is a chain in the same order. More...
struct	dedekind::category::detail_comprehension::SubrangeAt< R >
struct	dedekind::category::Windows
	windows(n), the stage that reads each position's window of n elements, a position with its context, as a comonad's \(\delta\) would on an infinite stream; on a finite range the last n - 1 positions have no full window, so it is not a comonad here. It is std::views::slide(n), spelled as a stage. More...
struct	dedekind::category::detail_comprehension::KernelAt< T, K >
	The kernel at one more prefix. More...
struct	dedekind::category::LastOf< T >
	The history comonad's counit: a prefix's last letter. More...
struct	dedekind::category::detail_comprehension::LengthOf
	A kernel for the laws: a prefix's length. More...
struct	dedekind::category::detail_comprehension::KeepsWhatItClassifies
struct	dedekind::category::WindowJoin< P, S >
	p >> s, SQL's JOIN on a window: the tensor of the windows of the words of p that land in s, at every offset where a window fits. A constructor, not a materialisation: the join is a tensor, counted, never enumerated, so it stays inside the counted world and never meets the bag a join yielding rows would need. More...
struct	dedekind::category::Offsets< N >
	The offsets a window takes, as a tensor: the chain of m, its count m, one factor \(m^1\). Its outer product with a tensor is the copower \(m \cdot X\), m copies, the action of \(\mathbb{N}\) on the counts (:action; Listing 4's concat on copies). Fubini's sum over the offsets, every summand the same (period 1, translation invariance), is this factor of the product. More...
struct	dedekind::category::JoinWith< P, S >
	join_with(p), a set of words to its join with p on the window: the join curried in the set, an arrow between tensors, its exponential transpose (curry, :cartesian); each join the pullback along the window (IsPullback, :pullback). More...
struct	dedekind::category::Counting< J >
	counting, a counted tensor to its count: the reading that ends a pipeline of arrows, as count ends a query. The cardinality, strong monoidal from \(\otimes\) to \(\times\) (the box law read on counts), modulo the word: a ranking by it is a ranking of the exact counts only while they fit, which the law's plan, evaluating no count, does not need and the fused pass does (#1134). More...
struct	dedekind::category::detail_comprehension::JoinWithStage< P >
struct	dedekind::category::detail_comprehension::CountingStage
struct	dedekind::category::detail_comprehension::Counted
	The count of a query, as Maybe's action: a query that may not be, counted where it is. More...
struct	dedekind::category::antitone_on_even_lengths< Rank >
	A rank whose values do not grow along the even lengths, so that ranking the even lengths descending reads them upwards. Derived, not registered per rank: a family's occurrences in the words of length N are \((N - n + 1)\) offsets times its density times \(|\Sigma|^N\), a product of non-negative sequences that do not grow, which does not grow either. The product law, stated here for the join's exact count; a general one belongs in :posetal, on an exact carrier or on an extent, since a word's × wraps and an antitone product past it is not antitone (#1134). More...
struct	dedekind::category::antitone_on_even_lengths< Compose< Compose< Fam, JoinWith< P, S > >, Counting< J > > >
struct	dedekind::category::OrderBy< Rank, Order >
	order_by(rank), SQL's ORDER BY: the stage that sorts a query by rank under Order, a strict weak order on the ranks. Ties are SQL's: which of the tied elements a take keeps, and in which order, is the plan's (a law's rewrite reads them in the walk's order or its reversal, the fused pass in the walk's); a rank without ties orders alike under every plan. More...
struct	dedekind::category::Take< K >
	take<K>(), SQL's LIMIT: the first K present elements. More...
struct	dedekind::category::detail_comprehension::ascends_by_position< F >
	The trait behind AscendsByPosition: an arrow over the positions whose present elements rise with the position, so that a query read through it is sorted by construction. A struct, so that a family registers by one partial specialisation. More...
struct	dedekind::category::detail_comprehension::ascends_by_position< Where< P > >
	where keeps the positions it keeps: a filtered chain is a chain in the same order. More...
struct	dedekind::category::detail_comprehension::One
	An element's share of a take: one if present, none for a hole, read through Maybe's eliminator. More...
struct	dedekind::category::detail_comprehension::Taken< S, Coalg, K >
	The coalgebra of take<K>: the walk, until K elements are present. One more state, the count so far; O(1), no storage. More...
struct	dedekind::category::detail_comprehension::element_of< E >
	The value a query's element carries: the Maybe's, or the element itself in a plain sequence. More...
struct	dedekind::category::detail_comprehension::element_of< Maybe< T > >
struct	dedekind::category::detail_comprehension::Read< T, K >
	The coalgebra reading a bounded list position by position, each element present: a value on the stack walked as any query, so every stage composes after it. More...
struct	dedekind::category::detail_comprehension::Pending< Q, Rank, Order >
	order_by without a law to read, pending its take: it needs the whole query, so only the fused order_by >> take<K> is offered, never the sort alone (it would need the caller's buffer). More...
struct	dedekind::category::detail_comprehension::Before< Rank, Order >
	Whether a ranks before b. More...
struct	dedekind::category::detail_comprehension::KeepBest< T, K, Rank, Order >
	One more element into the best K so far, sorted by the rank: inserted after those it does not rank before, so ties keep the walk's order, and the last cut where the list overflows. O(K) on the stack. More...
struct	dedekind::category::detail_comprehension::Progression< N >
	The progression \(j \mapsto m j + r\), a residue class's members in order: a congruence filter on a chain read as a chain of its own. More...
struct	dedekind::category::detail_comprehension::bound_of< Coalg >
	The most elements a walk presents: a take's K, or a bounded list's, kept by each SELECT and WHERE after it (a map presents no more than it reads). No member where nothing bounds the walk. More...
struct	dedekind::category::detail_comprehension::bound_of< Taken< S, Coalg, K > >
struct	dedekind::category::detail_comprehension::bound_of< Read< T, K > >
struct	dedekind::category::detail_comprehension::bound_of< Mapped< S, Coalg, F > >

Namespaces
namespace	dedekind::category
namespace	dedekind::category::detail_comprehension

Concepts
concept	dedekind::category::detail_comprehension::IsMaybe
concept	dedekind::category::detail_comprehension::ReadsItsElements
	A stage that reads a query's elements: an arrow out of the type its present elements have.
concept	dedekind::category::IsQuery
	A query: a range whose elements are Maybe, each present or a hole.
concept	dedekind::category::detail_comprehension::IsForeignView
	A view of the caller's, not one of the library's walks.
concept	dedekind::category::IsPrefixKernel
	A kernel on the non-empty prefixes of a text: an arrow out of them, a coKleisli arrow of the history comonad, whose answer at a position may read all that came before it and nothing after.
concept	dedekind::category::detail_comprehension::AscendsByPosition
concept	dedekind::category::detail_comprehension::KeptByTheWalk
	The walk's own order already is Order's under Rank: the chain descends by prior, so its elements fall along it, and a monotone rank under descending, or an antitone one under ascending, keeps them in order. order_by is then the identity.
concept	dedekind::category::detail_comprehension::ReversedByTheWalk
	The walk's order is Order's reversed: order_by is the query re-rooted on the ascending slice, read upwards.
concept	dedekind::category::detail_comprehension::IsBounded

Typedefs
using	dedekind::category::detail_comprehension::Evens = Subobject<std::size_t, Congruent<>>
using	dedekind::category::ascending = std::less<>
	The orders a query is sorted by, the standard's comparisons named as SQL's ASC and DESC: the defaults of order_by's parameter, which takes any comparison with sufficient structure, a total preorder on the rank's values.
using	dedekind::category::descending = std::greater<>

Functions
template<std::semiregular Op>
constexpr Lifted< Op >	dedekind::category::lifted (Op op)
template<IsArrow P> requires std::same_as<Cod<P>, bool>
constexpr Where< P >	dedekind::category::where (P p)
template<detail_comprehension::IsForeignView R, IsArrow F> requires std::invocable<const F&, std::ranges::range_reference_t<R>>
constexpr auto	dedekind::category::operator>> (R r, F f)
	r >> f on a range of the caller's: f on each element, which is std::views::transform.
constexpr void	dedekind::category::detail_comprehension::refuse_window_width ()
	Refuses a window of no letters, or wider than a range's distance type counts: the standard's slide has no such view.
template<std::ranges::view R> requires std::ranges::random_access_range<R> && std::ranges::sized_range<R>
constexpr auto	dedekind::category::detail_comprehension::sliding (R r, std::size_t n)
constexpr Windows	dedekind::category::windows (std::size_t n)
template<detail_comprehension::IsForeignView R> requires std::ranges::forward_range<R>
constexpr auto	dedekind::category::operator>> (R r, Windows w)
template<typename T, IsPrefixKernel< T > K>
constexpr auto	dedekind::category::scan (K k, std::span< const T > s)
	scan(k, s), the extension of the history comonad: a kernel asked at every non-empty prefix, SQL's window function over ROWS UNBOUNDED PRECEDING, as scan on a Path (:sequences). Every position has a prefix, so unlike a window of n this is a comonad on a finite range; each answer may read the whole prefix, so a kernel that factors through finitely many states has an overload of its own (:automaton).
constexpr bool	dedekind::category::detail_comprehension::lazy_is_the_functor ()
template<typename P, typename S, IsArrow T>
constexpr auto	dedekind::category::where (const Symmetric< P, S, T > &s)
	where(section): the windows a section holds, its membership as the filter, where(sites). The section stays a tensor (its * is the outer product); only here is it read as a predicate, its characteristic map, an arrow from a window of its letters: a std::span, since an arrow has one domain and a text is contiguous (a genome's bytes, Listing 5's carrier). The membership itself reads any random-access range; a window of a non-contiguous container is tested by it directly, not through this stage.
template<detail_comprehension::IsForeignView R, typename P, typename S, IsArrow T> requires requires(R r, const Symmetric<P, S, T>& s) { std::move(r) >> windows(1uz) >> where(s); }
constexpr auto	dedekind::category::operator>> (R r, const Symmetric< P, S, T > &s)
	r >> s: where the words of a section occur in a range of the caller's: its windows of the section's length, each kept where the section holds it. The section knows its length, so no window of another arises. Listing 5's dna >> pali6, the same expression as the join below read at one sequence.
template<std::regular S, std::semiregular Coalg, IsArrow F> requires detail_comprehension::ReadsItsElements<unfold_view<S, Coalg>, F>
constexpr auto	dedekind::category::operator>> (const unfold_view< S, Coalg > &q, F f)
	>> f on a query, SQL's SELECT: f on the present elements, the holes passed through, Maybe's action on the arrow (maybe_functor).
template<std::regular S, std::semiregular Coalg, IsArrow F> requires detail_comprehension::ReadsItsElements<unfold_view<S, Coalg>, F> && detail_comprehension::IsMaybe<Cod<F>>
constexpr auto	dedekind::category::operator>> (const unfold_view< S, Coalg > &q, F f)
	>> f on a query with f a Kleisli arrow into Maybe, a second where among them: Kleisli composition, f extended by Maybe's κ (:kleisli), so the holes do not nest. Filter fusion, where(p) >> where(q) = where(p ∧ q), is then the monad's associativity, not a rewrite of this partition's.
template<IsCountWord N, typename P, typename Q> requires requires(const P& p, const Q& q) { { p & q } -> IsArrow; requires std::same_as<Cod<decltype(p& q)>, bool>; }
constexpr auto	dedekind::category::operator>> (const FiniteChainSequence< N, Where< P > > &q, const Where< Q > &w)
	where(p) >> where(q) on a chain, fused by type: one where whose predicate is the lattice term p & q, the meet in the Boolean algebra of the chain's subobjects (:lattice's Meet). The filter is then a term the lattice's laws and the periodic counts read, not two walks; where p & q is not formed, the Kleisli composite above takes the query.
template<IsCountWord N, HasPeriod P> requires std::same_as<Cod<P>, bool>
constexpr N	dedekind::category::count (const FiniteChainSequence< N, Where< P > > &q)
	The count of a chain under a periodic filter: the count of the filter's characteristic sequence, which :periodic takes period by period (the lcm for a meet), no walk of the query. The law count(where(p)) = count(χ_p), used as the rewrite.
template<IsCountWord N = std::size_t, IsQuery Q>
constexpr N	dedekind::category::count (Q q)
	The count of a query, SQL's COUNT: its present elements, the tally lifted through Maybe.
template<IsQuery Q, IsCountWord N = typename std::ranges::range_value_t< Q>::value_type>
constexpr N	dedekind::category::sum (Q q)
	The sum of a query of counts, SQL's SUM: + lifted through Maybe.
template<HasNNOStep C, IsArrow F, IsCountWord N, typename P, typename S, IsArrow T> requires requires(const Power<C, F, N>& p, const Symmetric<P, S, T>& s) { occurrences(p, s); }
constexpr WindowJoin< Power< C, F, N >, Symmetric< P, S, T > >	dedekind::category::operator>> (const Power< C, F, N > &p, const Symmetric< P, S, T > &s)
template<IsCountWord N>
constexpr AtMost< Factor< N >, 1 >	dedekind::category::count_factors (const Offsets< N > &o)
template<typename P, typename S> requires requires(const P& p, const S& s) { occurrences(p, s); }
constexpr auto	dedekind::category::explain (const WindowJoin< P, S > &j)
	The plan of a join on the window, EXPLAIN: the offsets times the cylinder at the first, an outer product, the cylinder in turn its selection pushed down (pushed_down). Fubini, periodicity and the box law compose into it; none of the three is stated for joins. Its type is the plan, so a test asserts it. Defined where a window fits.
template<typename P, typename S> requires requires(const P& p, const S& s) { occurrences(p, s); }
constexpr auto	dedekind::category::count_factors (const WindowJoin< P, S > &j)
	The factors of a join's count: its plan's, the box law throughout, with no sum over the offsets left; none where no window fits.
template<typename P, typename S> requires requires(const P& p, const S& s) { occurrences(p, s); }
constexpr auto	dedekind::category::count (const WindowJoin< P, S > &j)
template<typename P, typename S> requires requires(const P& p, const S& s) { occurrences(p, s); }
constexpr auto	dedekind::category::exact_count (const WindowJoin< P, S > &j)
template<typename P>
constexpr detail_comprehension::JoinWithStage< P >	dedekind::category::join_with (P p)
template<IsArrow Fam, typename P> requires requires(const P& p, const Cod<Fam>& s) { occurrences(p, s); }
constexpr auto	dedekind::category::operator>> (const Fam &fam, const detail_comprehension::JoinWithStage< P > &st)
template<IsArrow F> requires requires(const Cod<F>& j) { count(j); }
constexpr auto	dedekind::category::operator>> (const F &f, detail_comprehension::CountingStage)
template<IsQuery Q>
constexpr std::size_t	dedekind::category::operator>> (Q q, detail_comprehension::CountingStage)
	q >> counting, the stage form of count(q): the fold that ends a query, in the query's own rhythm.
template<IsQuery Q>
constexpr Maybe< std::size_t >	dedekind::category::count (const Maybe< Q > &q)
	A query that may not be (a plan past its capacity), counted: the count lifted through Maybe, nothing where the query is nothing. The monad carries the uncertainty to the end, so no caller cases on it.
template<IsQuery Q>
constexpr Maybe< std::size_t >	dedekind::category::operator>> (const Maybe< Q > &q, detail_comprehension::CountingStage)
	The stage form of the same.
template<typename Order = ascending, IsArrow Rank> requires std::strict_weak_order<const Order&, Cod<Rank>, Cod<Rank>>
constexpr OrderBy< Rank, Order >	dedekind::category::order_by (Rank rank, Order order={})
template<std::size_t K>
constexpr Take< K >	dedekind::category::take ()
template<typename T>
constexpr std::size_t	dedekind::category::detail_comprehension::present (const Maybe< T > &e)
template<typename T>
constexpr std::size_t	dedekind::category::detail_comprehension::present (const T &)
template<std::semiregular T, std::size_t K>
constexpr unfold_view< std::size_t, Read< T, K > >	dedekind::category::detail_comprehension::walk (const AtMost< T, K > &list)
template<IsCountWord N, typename F, IsArrow Rank, typename Order> requires std::same_as<Dom<Rank>, N> && detail_comprehension::AscendsByPosition<F> && detail_comprehension::KeptByTheWalk<Rank, Order>
constexpr FiniteChainSequence< N, F >	dedekind::category::operator>> (const FiniteChainSequence< N, F > &q, const OrderBy< Rank, Order > &)
	order_by on a filtered chain whose rank keeps the walk's order: the identity, the query sorted by construction (rewrite 3).
template<IsCountWord N, typename F, IsArrow Rank, typename Order> requires std::same_as<Dom<Rank>, N> && detail_comprehension::AscendsByPosition<F> && detail_comprehension::ReversedByTheWalk<Rank, Order>
constexpr auto	dedekind::category::operator>> (const FiniteChainSequence< N, F > &q, const OrderBy< Rank, Order > &)
	order_by on a filtered chain whose rank reverses the walk's order: the query re-rooted on the ascending slice [0, n), read upwards, the positions where the walk read them downwards (rewrite 3).
template<std::ranges::input_range Q, IsArrow Rank, typename Order>
constexpr detail_comprehension::Pending< Q, Rank, Order >	dedekind::category::operator>> (Q q, OrderBy< Rank, Order > by)
	order_by with no law to read: pending its take.
template<std::regular S, std::semiregular Coalg, std::size_t K>
constexpr auto	dedekind::category::operator>> (const unfold_view< S, Coalg > &q, Take< K >)
	take<K> on a query or a sequence: the walk, until K elements are present, lazily (rewrite 1; on a sorted query, rewrite 3's first K).
template<std::size_t K, typename Q, typename Rank, typename Order>
constexpr auto	dedekind::category::detail_comprehension::fused_take (Pending< Q, Rank, Order > p)
	The fused plan of order_by >> take<K> with no law: one pass keeping the best K, the elements present. The pending query is owned, so a range iterable only when mutable folds too.
template<IsArrow F, typename J, IsCountWord N>
constexpr bool	dedekind::category::detail_comprehension::fits_the_word (const Compose< F, Counting< J > > &rank, N l)
	Whether a rank of lengths stays exact from length l on: its values do not grow there, so the largest is at l, and it fits the rank's word, the count's, where its factors say so (bits_needed): the product law's extent, decided by one count, before any is compared.
template<typename Q, typename Rank, typename Order, std::size_t K>
constexpr auto	dedekind::category::operator>> (detail_comprehension::Pending< Q, Rank, Order > p, Take< K >)
	order_by >> take<K> with no law: fused, one pass keeping the best K in an AtMost, never sorting the whole (rewrite 2). A query still, each element present, so its count is its rows' and collect makes the plain list.
template<IsCountWord N, typename Rank, std::size_t K> requires std::same_as<Dom<Rank>, N> && antitone_on_even_lengths<Rank>::value
constexpr auto	dedekind::category::operator>> (const detail_comprehension::Pending< unfold_view< std::optional< N >, detail_chain::SliceStep< N, Where< Congruent< N > > > >, Rank, descending > &p, Take< K >)
	The lengths in a residue class, ranked by their occurrences, the first K: one plan compiled, the even case, and the run time only reindexing into it. A family whose density falls along the even lengths ranks them by construction, the shortest first (the walk read upwards, rewrite 3), so the first K need no rank evaluated at all. A residue class of even modulus holds lengths of one parity: even ones are the case; odd ones occur nowhere (the reversal pairs the letters, and no even alphabet fixes them all), all ranked alike. Either way the class's members in order are the plan, a progression: padded into the class by \(j \mapsto m j + r\), unpadded by reading the lengths back. An odd modulus mixes the parities and takes the fused pass.
template<std::regular S, std::semiregular Coalg> requires detail_comprehension::IsBounded<Coalg>
constexpr auto	dedekind::category::collect (const unfold_view< S, Coalg > &q)
	A query's present elements as a value, bounded by its take: the ext boundary, where a list is asked for (#1133). A plain sequence's elements as they are, a query's unwrapped.

Variables
template<typename T>
constexpr bool	dedekind::category::detail_comprehension::is_maybe_v = false
	Whether T is a Maybe: an element of a query, or none.
template<typename T>
constexpr bool	dedekind::category::detail_comprehension::is_maybe_v< Maybe< T > > = true
template<typename R>
constexpr bool	dedekind::category::detail_comprehension::is_walk_v = false
template<std::regular S, std::semiregular Coalg>
constexpr bool	dedekind::category::detail_comprehension::is_walk_v< unfold_view< S, Coalg > > = true
constexpr std::array< std::size_t, 3 >	dedekind::category::detail_comprehension::history_witness {7, 8, 9}
constexpr std::array< std::size_t, 5 >	dedekind::category::detail_comprehension::functor_witness {0, 1, 2, 3, 4}
constexpr std::array< std::byte, 6 >	dedekind::category::detail_comprehension::gaattc
constexpr detail_comprehension::CountingStage	dedekind::category::counting {}
	The stage counting what precedes it.

Detailed Description

Monad comprehensions over a finite chain: the queries of SQL and LINQ, where, select, order_by and take, and the folds that end them.

@partition :comprehension

One carrier, one rhythm

Every stage takes a query and returns a query, composed by >>, as Python's [f(x) for x in xs if p(x)] and SQL's SELECT ... WHERE do.

LINQ	SQL	here
from	FROM	n >> chain<N>()
Select	SELECT	>> f
Where	WHERE	>> where(p)
Join	JOIN	p >> s
OrderBy	ORDER BY	>> order_by(rank)
Take	LIMIT	>> take<K>()
-	OVER	>> windows(n)
Count	COUNT	count, >> counting
Sum	SUM	sum

The names are the common ones; where a name is the category theory's, the comprehension takes another: take, Haskell's and LINQ's, for SQL's LIMIT, since a limit here is the universal construction (:limit), and the monad's multiplication is μ; SQL's JOIN keeps no name of its own, being a power read through a set of words, the bind.

The carrier is a finite chain sequence holding at most one element per position: the list monad whose Kleisli arrows yield none or one, so a query is a chain read through a Kleisli arrow into Maybe. where is that arrow; select after it is Maybe's action on arrows; a fold ends the query, its step lifted once through Maybe's eliminator, so no consumer cases on a hole. A plain sequence has no holes and stays unlifted, by its type. The rewrites a query optimiser applies are laws of the monad and of the algebra: Wadler's comprehensions over any monad (1990), the comprehension syntax of Buneman, Libkin, Suciu, Tannen and Wong as a query language (1994), Grust's optimiser on its laws (#1133). A join yielding several rows per input leaves the carrier, a bag's; its count is the tensor products' (:periodic), never materialised.

Copyright

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