The Path (Morphism of Enumeration): a monad and a comonad. More...

#include <algorithm>
#include <array>
#include <cassert>
#include <compare>
#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <limits>
#include <memory>
#include <optional>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
import dedekind.order;
import dedekind.relational;
import dedekind.sequences:net;
import dedekind.sets;
import dedekind.category;

Include dependency graph for path.cppm:

Classes
class	dedekind::sequences::Path< T, Cardinality, Index >
	A sequence F: ℕ → T. More...
struct	dedekind::sequences::Path< T, Cardinality, Index >::const_iterator
struct	dedekind::sequences::SequenceGraph< PathT >
	`as_relation(path)` — adapt a `Path<T>` into its graph relation, a Set of (index, value) pairs. More...
struct	dedekind::category::path_functor< T >
	The path functor for the `Path` <·> shape (#508 / PR #521 review). More...
struct	dedekind::category::unit_witness< path_functor< T >, T >
struct	dedekind::category::counit_witness< path_functor< T >, T >
struct	dedekind::category::is_kleisli_triple< dedekind::sequences::path_functor< T > >
	A path with the default (infinite) cardinality is a stream, whose bind is the diagonal and whose extend takes suffixes: the monad and the comonad on streams (Uustalu and Vene), their laws by construction. More...
struct	dedekind::category::is_cokleisli_triple< dedekind::sequences::path_functor< T > >

Namespaces
namespace	dedekind::category
namespace	dedekind::sequences::_path_525

Concepts
concept	dedekind::sequences::IsStreamComonad
	\emph{Operational} duck-typed check that `W` carries the Uustalu–Vene stream-comonad shape on an infinite sequence \(\mathbb{N} \to A\). The concept body checks the two primitive legs — `ε` (head `w.at(0)`) and `δ` (`tails(w)`) — only; the third leg `extend` (`w` `<<=` `f`) is the derived \(\mathrm{map}\,f \circ \delta\) and is certified separately by the `IsCoKleisliTriple` witness (pinned beside the `IsStreamComonad<Path<int>>` assertion below), not re-checked here.

Typedefs
template<typename T>
using	dedekind::sequences::FinitePath = Path<T, Finite>
using	dedekind::sequences::_path_525::PathArrow = dedekind::category::CanonicalSetCCC<Path<int>>::Arrow
template<typename T>
using	dedekind::sequences::Sequence = Path<T>
	Textbook name: a Sequence over `T` is `f` : ℕ → T = `Path<T>`.
template<typename T, typename D = std::size_t>
using	dedekind::sequences::Net = Path<T>
	Textbook name: a Net is a function from a directed set into `T`.

Functions
template<typename T>
constexpr const FinitePath< T > &	dedekind::sequences::as_range (const FinitePath< T > &path)
template<typename R> requires std::ranges::input_range<R>
constexpr auto	dedekind::sequences::from_range (R &&range)
template<typename T, typename Cardinality, typename Index>
constexpr auto	dedekind::sequences::prefix (const Path< T, Cardinality, Index > &path, std::size_t length)
template<typename T, typename Cardinality, typename Index> requires (!dedekind::sets::IsFinite<Cardinality>)
constexpr auto	dedekind::sequences::drop (const Path< T, Cardinality, Index > &path, std::size_t n)
template<typename T, typename Cardinality, typename Index> requires std::equality_comparable<T>
constexpr auto	dedekind::sequences::as_relation (const Path< T, Cardinality, Index > &path)
template<typename T, typename Cardinality, typename Index> requires (!dedekind::sets::IsFinite<Cardinality>)
constexpr auto	dedekind::sequences::tails (const Path< T, Cardinality, Index > &s) -> Path< Path< T, Cardinality, Index >, Cardinality, Index >
	δ (duplicate / comultiplication) of the stream comonad — the stream of all suffixes.
template<typename T, typename Step> requires std::invocable<const std::decay_t<Step>&, const T&> && std::same_as< std::invoke_result_t<const std::decay_t<Step>&, const T&>, T>
constexpr auto	dedekind::sequences::iterate (T seed, Step &&step)
template<typename T, typename Step> requires std::invocable<const std::decay_t<Step>&, const T&> && std::same_as< std::invoke_result_t<const std::decay_t<Step>&, const T&>, T>
constexpr auto	dedekind::sequences::iterate (T seed, Step &&step, std::size_t length)
template<typename Op, typename T, typename... Ts> requires (std::convertible_to<Ts, T> && ...) && std::invocable<const Op&, T, Ts...> && std::same_as< std::remove_cvref_t<std::invoke_result_t<const Op&, T, Ts...>>, T>
constexpr Path< T >	dedekind::sequences::iterate (Op op, T seed_0, Ts... more_seeds)
	`iterate`(op, `seed_0`, ... , `seed_{n-1}`) — n-ary recurrence: a binary (or n-ary) operator applied repeatedly to a sliding window of `n` previous values.
template<typename T, typename Cardinality, typename Index, typename Pred> requires dedekind::sets::IsFinite<Cardinality> && std::predicate<const std::decay_t<Pred>&, const T&>
constexpr std::size_t	dedekind::sequences::count_if (const Path< T, Cardinality, Index > &path, Pred &&pred)
template<typename T, typename Pred> requires std::copy_constructible<std::decay_t<Pred>> && std::predicate<const std::decay_t<Pred>&, const T&>
constexpr std::optional< std::size_t >	dedekind::sequences::first_where (const Path< T > &path, Pred &&pred, std::size_t budget)
template<typename T, typename Pred> requires std::copy_constructible<std::decay_t<Pred>> && std::predicate<const std::decay_t<Pred>&, const T&>
constexpr std::optional< std::size_t >	dedekind::sequences::first_where (const FinitePath< T > &path, Pred &&pred)
template<typename T, typename Cardinality, typename Index, typename Pred> requires std::predicate<const std::decay_t<Pred>&, const T&>
constexpr auto	dedekind::sequences::exists (const Path< T, Cardinality, Index > &path, Pred &&pred)
template<typename T, typename Index, typename F> requires std::copy_constructible<std::decay_t<F>> && std::invocable<const std::decay_t<F>&, const Path<T, Finite, Index>&>
constexpr auto	dedekind::sequences::scan (F &&f, const Path< T, ℵ_0, Index > &path) -> Path< std::invoke_result_t< const std::decay_t< F > &, const Path< T, Finite, Index > & >, ℵ_0, Index >
	Co-Kleisli scan: apply a prefix aggregate to each initial segment.
template<typename T, typename Cardinality, typename Index, typename Pred> requires std::predicate<const std::decay_t<Pred>&, const T&>
constexpr auto	dedekind::sequences::forall (const Path< T, Cardinality, Index > &path, Pred &&pred)

Variables
template<typename I, typename T, typename L, typename PathT, typename C>
constexpr bool	dedekind::category::is_right_unique_v< dedekind::sets::Comprehension< dedekind::sets::𝔸< std::pair< I, T >, L, C >, dedekind::sequences::SequenceGraph< PathT > > >
template<typename I, typename T, typename L, typename PathT, typename C>
constexpr bool	dedekind::category::is_left_total_v< dedekind::sets::Comprehension< dedekind::sets::𝔸< std::pair< I, T >, L, C >, dedekind::sequences::SequenceGraph< PathT > > >

Detailed Description

The Path (Morphism of Enumeration): a monad and a comonad.

@partition :path

path__The_Path_Morphism

Following the Dedekind structuralist tradition, a Path is a functional mapping (λn. s_n) from the Countable Index (ℕ) to a Species (T).

The_Monad_And_Comonad

A Path satisfies both the Monadic (Push) and Comonadic (Pull) extension systems, though not the Frobenius law relating them (IsFrobenius):

Kleisli (Monad) : Enables 'flattening' of nested paths via diagonal sampling (Bind).
Co-Kleisli (Comonad): Enables 'contextual' transformations such as running averages or finite differences (Extend).

@build_order 5 @dependency dedekind.category, dedekind.sequences:sequences

Wikipedia: Sequence, Monad (category theory), Comonad

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

Note: "I am striking out a new path for myself." – Srinivasa Ramanujan, letter to G. H. Hardy (16 January 1913)

Typedef Documentation

◆ Net

template<typename T, typename D = std::size_t>

using dedekind::sequences::Net = Path<T>

export

Textbook name: a Net is a function from a directed set into T.

For now ℕ is the only directed-set domain we model concretely, so Net<T> = Path<T> in this library. The requires clause pins D = std::size_t (i.e., ℕ) so that callers cannot quietly instantiate over a non-ℕ domain that the library does not yet support. Once :order grows non-ℕ directed-set carriers, the right move is to redesign Net as a struct or concept (alias templates cannot be specialised), with this typedef-shape replaced by the more general definition. The constraint here is the forward-pointing marker for that future redesign, not a specialisation hook.

Function Documentation

◆ drop()

template<typename T, typename Cardinality, typename Index>
requires (!dedekind::sets::IsFinite<Cardinality>)

auto dedekind::sequences::drop	(	const Path< T, Cardinality, Index > &	path,
		std::size_t	n )

constexprexport

Return the infinite tail of a path, shifted by n indices.

drop(path, n) = λi. path(n + i)

Template Parameters

T	The element type.
Cardinality	The cardinality of the input path (must be infinite).

Parameters

path	The input path (must have infinite cardinality).
n	The offset to drop. Precondition: for each accessed index i, the sum n + i must be representable in std::size_t.

Returns: An infinite path with the same cardinality, representing the shifted tail.

◆ first_where()

template<typename T, typename Pred>
requires std::copy_constructible<std::decay_t<Pred>> && std::predicate<const std::decay_t<Pred>&, const T&>

std::optional< std::size_t > dedekind::sequences::first_where	(	const Path< T > &	path,
		Pred &&	pred,
		std::size_t	budget )

constexprexport

Find the first index where a predicate holds, up to an inclusive budget.

first_where(path, pred, n) ≡ min { k ≤ n | pred(path(k)) }, or nullopt.

Two overloads: infinite path with explicit budget, finite path self-bounded.

◆ iterate()

template<typename Op, typename T, typename... Ts>
requires (std::convertible_to<Ts, T> && ...) && std::invocable<const Op&, T, Ts...> && std::same_as< std::remove_cvref_t<std::invoke_result_t<const Op&, T, Ts...>>, T>

Path< T > dedekind::sequences::iterate	(	Op	op,
		T	seed_0,
		Ts...	more_seeds )

constexprexport

iterate(op, seed_0, ... , seed_{n-1}) — n-ary recurrence: a binary (or n-ary) operator applied repeatedly to a sliding window of n previous values.

Captures the structural pattern "binary @em op @em applied @em recursively" that recurs across the codebase's recurrence exhibits (Fibonacci, Lucas, Tribonacci, GCD-via-Euclid, linear recurrences of any order). The state is a sliding window of n carriers; each step computes op(w_0, ..., w_{n-1}) , shifts the window left by one, and writes the result into the last slot. The read-back semantics: path.at(k) for k < n returns seed_k ; for k >= n returns the canonical k -th sequence element.

path__nary_iterate_Use

// Fibonacci:         F_0 = 0, F_1 = 1, F_{n+2} = F_n + F_{n+1}
auto fib = iterate(std::plus<size_t>{}, size_t{0}, size_t{1});
// Path<size_t>, at(0)=0, at(1)=1, at(2)=1, at(3)=2, ...
 
// Tribonacci:        T_{n+3} = T_n + T_{n+1} + T_{n+2}
auto tri = iterate([](size_t a, size_t b, size_t c) { return a + b + c; },
                   size_t{0}, size_t{0}, size_t{1});
 
// Generic linear recurrence (e.g. Pell's: P_{n+1} = 2 P_n + P_{n-1}):
auto pell = iterate([](size_t a, size_t b) { return 2*b + a; },
                    size_t{0}, size_t{1});

path__nary_iterate_NNO_Reading

For n = 1 this overload reduces to the standard NNO morphism iterate(op, seed) above (in argument-swapped form) — the categorical NNO universal property says there exists a unique morphism ℕ → carrier making the recursion diagram commute (Mac Lane CWM §V.5), and this is the n -dimensional analogue. The existing 2-argument iterate(seed, step) form stays alongside this overload for back-compat; new code is encouraged to prefer the n-ary form for any recurrence of order >= 2 .

Template Parameters

Op	An `n` -ary callable on `T` `×` ... `×` `T` returning `T` (where `n` `=` `1` `+` `sizeof`...(Ts) ).
T	The carrier of the recurrence; the codomain of `op` .
Ts	Additional seed types convertible to `T` .

@complexity O(k) per path.at(k) call — the lazy form walks from the seeds on each random access, just like the binary iterate above. The eager bounded sibling is a separate slice deferred until a use case surfaces.

◆ scan()

template<typename T, typename Index, typename F>
requires std::copy_constructible<std::decay_t<F>> && std::invocable<const std::decay_t<F>&, const Path<T, Finite, Index>&>

auto dedekind::sequences::scan	(	F &&	f,
		const Path< T, ℵ_0, Index > &	path )->Path< std::invoke_result_t< conststd::decay_t< F > &, constPath< T, Finite, Index > & >, ℵ_0, Index >

constexprexport

Co-Kleisli scan: apply a prefix aggregate to each initial segment.

Produces an infinite path where element i is f(prefix(path, i+1)).

This is the canonical SQL window-function pattern over an ordered sequence: scan(sum, path)(i) == sum of path[0..i] scan(exists(pred), path)(i) == exists(prefix(path, i+1), pred)

Relation to operator<<=: scan(f, path) is the co-Kleisli extension of [f](ctx) { return f(prefix(ctx, 1)); }, expressed without the suffix-path construction. Note that operator<<= passes a suffix (drop) as context, while scan passes a prefix — these are the two canonical window shapes.

Parameters

f	Aggregate: FinitePath<T> → U (e.g. exists, forall, count_if).
path	Source infinite path.

Returns: Infinite Path where element i == f(prefix(path, i+1)).

◆ tails()

template<typename T, typename Cardinality, typename Index>
requires (!dedekind::sets::IsFinite<Cardinality>)

auto dedekind::sequences::tails ( const Path< T, Cardinality, Index > & s ) ->Path< Path< T, Cardinality, Index >, Cardinality, Index >

constexprexport

δ (duplicate / comultiplication) of the stream comonad — the stream of all suffixes.

For an infinite stream \(s : \mathbb{N} \to T\),

\[ \mathrm{tails}(s)\,(n) \;=\; \mathrm{drop}(s, n) \;=\; \lambda i.\, s(n+i), \]

so tails(s) is the \(\mathbb{N} \to (\mathbb{N} \to T)\) stream whose \(n\)-th element is the \(n\)-shifted tail of s. This is the Uustalu–Vene comultiplication \(\delta\) for the stream comonad; paired with the head counit \(\varepsilon(s) = s(0)\) it satisfies the comonad laws (witnessed in stream_comonad_test.cpp):

left counit: \(\varepsilon(\delta\,s) = s\) (head of tails)
right counit: \((\mathrm{map}\,\varepsilon)(\delta\,s) = s\)
coassoc: \(\delta(\delta\,s) = (\mathrm{map}\,\delta)(\delta\,s)\)

See also: operator<<= — the co-Kleisli extend; δ(s) is extend with the context-identity, i.e. s <<= std::identity{}.

Classes

Namespaces

Concepts

Typedefs

Functions

Variables

Detailed Description

path__The_Path_Morphism

The_Monad_And_Comonad

Typedef Documentation

◆ Net

Function Documentation

◆ drop()

◆ first_where()

◆ iterate()

path__nary_iterate_Use

path__nary_iterate_NNO_Reading

◆ scan()

◆ tails()