The matcher of a set of words of one length, specialised to it: the minimal automaton of \(\Sigma^* L\), a value computed by one constexpr function at either binding time. More...

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <cstdlib>
#include <functional>
#include <optional>
#include <ranges>
#include <span>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>
import dedekind.category:comprehension;

Include dependency graph for automaton.cppm:

Classes
struct	dedekind::category::Columns
	The column of a byte in a plan: its rank in the alphabet, as a table of the 256 bytes the compiler computes once, so that a scan does one load per letter where `Ranked` would count the letters below it. An entry is the rank plus one, zero for a byte outside the alphabet. A Kleisli arrow into `Maybe`, as `Ranked` is, and the same arrow by value. More...
struct	dedekind::category::detail_automaton::ColumnAt
	One byte's entry: its rank plus one, or zero. More...
struct	dedekind::category::Automaton< Sigma, Q >
	A matcher's plan: the transitions on each letter, and the states where a word of the set has just been read. More...
struct	dedekind::category::detail_automaton::Residual< N, P, K >
	A state: whether a word of the set has just been read, and the pending words by length, `pending`[k - 1] those of length `k`. More...
struct	dedekind::category::detail_automaton::DeriveSites< Sigma, N, KL >
	The set's own derivatives, one per letter: the same for every state, so computed once, before the walk. More...
struct	dedekind::category::detail_automaton::Advance< Sigma, N, P, K, KL >
	One pending length of a state's derivative by a letter: the pending words one longer, derived, and the set's own derivative where they are its length, joined; a word of length zero is a match. More...
struct	dedekind::category::detail_automaton::Build< Sigma, N, P, K, Q >
	The construction so far: the states found, in the order found, and the plan's rows for those already walked. More...
struct	dedekind::category::detail_automaton::Letter< Sigma, N, P, K, KL, Q >
	One letter out of the state being walked: its derivative's number, a new state numbered next where it is new. More...
struct	dedekind::category::detail_automaton::Walk< Sigma, N, P, K, KL, Q >
	One state walked, in the order found: its row of transitions, and whether it accepts. Past the states found, nothing to walk. More...
struct	dedekind::category::detail_automaton::Decode< Sigma, C, P, N >
	A code read back as its word: the digits in base `Sigma`, the first letter the most significant, each the letter of that rank. More...
struct	dedekind::category::detail_automaton::Decode< Sigma, C, P, N >::Digits
struct	dedekind::category::detail_automaton::Decode< Sigma, C, P, N >::Digit
struct	dedekind::category::detail_automaton::ReadBack< Section, Decoder >
	A code tested by a section: read back as its word, then the section's own membership. More...
struct	dedekind::category::detail_automaton::MirrorDigit< Sigma, N >
	One more digit of a half-site read backwards, reflected: the next letter of the other half, \(\sigma - 1 - d\) on the ranks. More...
struct	dedekind::category::detail_automaton::AddPalindrome< Sigma, N, KL >
	One more half-site, its word's code a run of one where it lies in the codes kept. Halves ascending give codes ascending, the half being the word's most significant digits. More...
struct	dedekind::category::detail_automaton::WithLetters< Sigma, Q >
	A plan with the columns of its alphabet's bytes. More...
struct	dedekind::category::detail_automaton::SetLetter
	One more letter of a power, into the set of them. More...
struct	dedekind::category::Prefix
	`prefix`("GA"): the words beginning with these letters, the predicate a section is met with. At most eight, the longest word a plan's menu holds. More...
struct	dedekind::category::detail_automaton::AddByte
	One more letter of a prefix. More...
struct	dedekind::category::Prefixed< P, S, T >
	A section met with a prefix. Its own type, so that only what knows the prefix reads it: `count_factors` reads cycle types alone, and would count the section as if no letter were fixed, so no count is offered until it has a law. More...
struct	dedekind::category::detail_automaton::NextByte
	One more byte of a word: its rank, the next digit. More...
struct	dedekind::category::Matches< Sigma, Q >
	`matches(plan)`, the stage that runs a matcher along a text: a query over the text's positions, present where a word of the plan's set ends. More...
struct	dedekind::category::detail_automaton::Cursor
	Where a run of the matcher is: its state and the next position. More...
struct	dedekind::category::detail_automaton::MatchStep< Sigma, Q, V >
	One position of the run: the state after its letter, and the position itself where that state accepts. O(1) state, the text read where it is. More...
struct	dedekind::category::detail_automaton::EndsInSite
	The kernel the table factors: whether a prefix ends in a word of the set, reading its last six letters and nothing kept. More...
struct	dedekind::category::detail_automaton::AgreesOnPrefix
	Whether the table and the windows agree on one more prefix. More...
struct	dedekind::category::detail_automaton::EndsInSubset
	The kernel the random words' table factors. More...
struct	dedekind::category::detail_automaton::RandomLaws
	What the seeds say: whether the laws hold on their words, and how many sites of the subset those held, so a vacuous run can be refused. More...
struct	dedekind::category::detail_automaton::LawsOnSeed

Namespaces
namespace	dedekind::category

Enumerations
enum class	dedekind::category::Holes : bool { break_match , skip }
	What a byte outside the alphabet does to a match: break it, the matcher back at its start (no word of the set holds the byte), or be skipped, the matcher as it was. Never a match itself.

Functions
constexpr Columns	dedekind::category::columns_of (const Letters &on)
template<std::size_t Sigma, IsCountWord N, std::size_t K>
constexpr auto	dedekind::category::detail_automaton::derived (const RunList< N, K > &r, N j, N a)
template<std::size_t Sigma, IsCountWord N, std::size_t P, std::size_t K, std::size_t KL>
constexpr Maybe< Residual< N, P, K > >	dedekind::category::detail_automaton::step (const Residual< N, P, K > &s, const std::array< RunList< N, KL >, Sigma > &own, N length, N a)
template<std::size_t Sigma, std::size_t P, std::size_t K, std::size_t Q, IsCountWord N, std::size_t KL>
constexpr Maybe< Automaton< Sigma, Q > >	dedekind::category::automaton (const RunList< N, KL > &sites, std::type_identity_t< N > length)
	The matcher specialised to a set of words of one length: the minimal automaton of \(\Sigma^* L\), canonical.
template<HasNNOStep C, IsArrow F, IsCountWord N>
constexpr AtMost< C, 257 >	dedekind::category::detail_automaton::letters_of (const Power< C, F, N > &p)
template<std::size_t KL, std::size_t Sigma, std::size_t P, HasNNOStep C, IsArrow F, IsCountWord N, typename S, IsArrow T>
constexpr Maybe< RunList< N, KL > >	dedekind::category::detail_automaton::tested_run_list (const Symmetric< Power< C, F, N >, S, T > &sites)
	Every code read back as its word and tested by the section.
template<std::size_t KL, std::size_t Sigma, std::size_t P, HasNNOStep C, IsArrow F, IsCountWord N, typename S, IsArrow T>
constexpr Maybe< RunList< N, KL > >	dedekind::category::run_list (const Symmetric< Power< C, F, N >, S, T > &sites)
	A section's words as a run list over their codes: each word read as its letters' ranks in base \(\sigma\), the first the most significant, so the chain \([0, \sigma^n)\) in the dictionary order. Every code is read back as its word and tested by the section's own membership: \(\sigma^n\) tests, the set enumerated once.
template<IsCountWord N>
constexpr bool	dedekind::category::detail_automaton::whole_alphabet (const Power< std::byte, Letters, N > &p)
template<std::size_t KL, std::size_t Sigma, IsCountWord N>
constexpr Maybe< RunList< N, KL > >	dedekind::category::detail_automaton::palindromes (N n, N prefix, N L)
	The palindromes of even length `n` among the codes [prefix, prefix + 1) \(\cdot \sigma^{n - L}\): only their half-sites are visited, none tested.
template<std::size_t KL, std::size_t Sigma, std::size_t P, IsCountWord N> requires (Sigma >= 4 && Sigma % 2 == 0)
constexpr Maybe< RunList< N, KL > >	dedekind::category::run_list (const Symmetric< Power< std::byte, Letters, N >, Reverse, Reflection > &sites)
	The words a reflection then the reversal fixes, listed by the law: a word is fixed by its half-site, so the \(\sigma^{n/2}\) halves are visited in order and no word is tested, where the general overload tests all \(\sigma^n\). This is what lets a small panel's table be built at compile time. With an even alphabet the reflection fixes no letter, and from four letters no two codes are adjacent, so each is a run of its own. An odd length, or a reflection other than the alphabet's own, is left to the general overload.
template<HasNNOStep C, IsArrow F, IsCountWord N>
constexpr Letters	dedekind::category::detail_automaton::effective_letters (const Power< C, F, N > &p)
template<std::size_t Sigma = 4, std::size_t P = 8, std::size_t K = 32, std::size_t Q = 320, std::size_t KL = 256, HasNNOStep C, IsArrow F, IsCountWord N, typename S, IsArrow T>
constexpr Maybe< Automaton< Sigma, Q > >	dedekind::category::automaton (const Symmetric< Power< C, F, N >, S, T > &sites)
	The matcher specialised to a section: its words as a run list, then the plan. The capacities default to a menu's largest, four letters, words of length 8, pending sets of 32 steps and 320 states, the one `pynzli` offers too, so `automaton(sites)` reads alike in both languages; a tighter bound is named where the plan is a constant.
constexpr Prefix	dedekind::category::prefix (std::string_view word)
template<typename P, typename S, IsArrow T>
constexpr Prefixed< P, S, T >	dedekind::category::operator& (const Symmetric< P, S, T > &s, const Prefix &p)
constexpr void	dedekind::category::detail_automaton::refuse_foreign_letter ()
	Refuses a word with a byte outside its alphabet.
template<std::size_t KL, std::size_t Sigma, std::size_t P, IsCountWord N> requires (Sigma >= 4 && Sigma % 2 == 0)
constexpr Maybe< RunList< N, KL > >	dedekind::category::run_list (const Prefixed< Power< std::byte, Letters, N >, Reverse, Reflection > &sites)
	The words of a section beginning with a prefix, by the law: no word tested, only the half-sites the prefix allows visited.
template<std::size_t Sigma = 4, std::size_t P = 8, std::size_t K = 32, std::size_t Q = 320, std::size_t KL = 256, IsCountWord N>
constexpr Maybe< Automaton< Sigma, Q > >	dedekind::category::automaton (const Prefixed< Power< std::byte, Letters, N >, Reverse, Reflection > &sites)
	The matcher of the words of a section beginning with a prefix. The same builder on a subset of the same words; capacities as for a section.
template<std::size_t Sigma, std::size_t Q>
constexpr std::size_t	dedekind::category::states (const Automaton< Sigma, Q > &plan)
template<std::size_t Sigma, std::size_t Q>
constexpr Matches< Sigma, Q >	dedekind::category::matches (const Automaton< Sigma, Q > &plan, Holes holes=Holes::break_match)
template<std::size_t Sigma, std::size_t Q>
constexpr Maybe< Matches< Sigma, Q > >	dedekind::category::matches (const Maybe< Automaton< Sigma, Q > > &plan, Holes holes=Holes::break_match)
	`matches` on a plan that may not be, `automaton(section)'s` `Maybe:` the stage, or nothing, by `Maybe's` action. The uncertainty of the capacity travels through the query to its count, so `dna` `>>` `matches(automaton(s))` `>>` `counting` is a `Maybe` count with no case on it in between.
template<std::ranges::view V, std::size_t Sigma, std::size_t Q> requires std::ranges::random_access_range<V> && std::ranges::sized_range<V> && std::semiregular<V>
constexpr auto	dedekind::category::operator>> (V letters, const Maybe< Matches< Sigma, Q > > &m)
constexpr void	dedekind::category::detail_automaton::refuse_no_letters ()
	Refuses bytes for a plan that knows no alphabet to read them in.
template<std::ranges::view V, std::size_t Sigma, std::size_t Q> requires std::ranges::random_access_range<V> && std::ranges::sized_range<V> && std::semiregular<V>
constexpr auto	dedekind::category::operator>> (V letters, const Matches< Sigma, Q > &m)
template<std::ranges::view V, std::size_t Sigma, std::size_t Q> requires std::ranges::random_access_range<V> && std::ranges::sized_range<V> && std::semiregular<V>
constexpr auto	dedekind::category::scan (const Automaton< Sigma, Q > &plan, V letters)
	`scan(plan, s)`: the history comonad's extension with its kernel factored through finitely many states, so that it keeps one state, not the history (Myhill and Nerode). It is `matches(plan)`, its holes breaking a match.
template<std::ranges::view V, std::size_t Sigma, std::size_t Q> requires std::ranges::random_access_range<V> && std::ranges::sized_range<V> && std::semiregular<V>
constexpr auto	dedekind::category::operator>> (V letters, const Automaton< Sigma, Q > &plan)
	`s` `>>` `scanner:` a plan read as the stage it is.
template<detail_comprehension::IsForeignView R, typename P, typename S, IsArrow T>
constexpr auto	dedekind::category::operator>> (R r, const Prefixed< P, S, T > &s)
	Where a prefixed section's words occur in a range of the caller's: the windows of its length it holds, as `r` `>>` `s` for a section.
constexpr Automaton< 4, 8 >	dedekind::category::detail_automaton::kmp_gaattc ()
constexpr bool	dedekind::category::detail_automaton::plan_factors_the_kernel ()
constexpr bool	dedekind::category::detail_automaton::table_is_the_kernel ()
constexpr bool	dedekind::category::detail_automaton::one_strand_is_enough ()
constexpr RandomLaws	dedekind::category::detail_automaton::on_random_words ()

Variables
template<>
constexpr bool	dedekind::category::is_kleisli_arrow_v< Ranked, maybe_monad_tag > = true
template<>
constexpr bool	dedekind::category::is_kleisli_arrow_v< Columns, maybe_monad_tag > = true
constexpr Automaton< 4, 8 >	dedekind::category::kmp_gaattc = detail_automaton::kmp_gaattc()
constexpr std::array< std::size_t, 15 >	dedekind::category::detail_automaton::ttgaattcaagctta
constexpr std::array< std::size_t, 12 >	dedekind::category::detail_automaton::gaattcgaattc
constexpr auto	dedekind::category::detail_automaton::law_section = power(abc("ACGT"), 6uz) & fixed_by(~rev)
constexpr auto	dedekind::category::detail_automaton::law_subset = law_section & prefix("GA")
constexpr auto	dedekind::category::detail_automaton::law_plan = *automaton<4, 6, 8, 12>(law_subset)
constexpr auto	dedekind::category::detail_automaton::law_text = bytes("GAATTCGAGCTCGGTACCCGGGGATCC")
constexpr auto	dedekind::category::detail_automaton::random_subset = law_section & prefix("AT")
constexpr auto	dedekind::category::detail_automaton::random_plan = *automaton<4, 6, 16, 32>(random_subset)
constexpr std::size_t	dedekind::category::detail_automaton::random_length = 24

Detailed Description

The matcher of a set of words of one length, specialised to it: the minimal automaton of \(\Sigma^* L\), a value computed by one constexpr function at either binding time.

@partition :automaton

The matcher as a coalgebra

A matcher reads a text letter by letter and reports where a word of L ends. Its state is what remains to be read for a match: a set of words, the derivative of \(\Sigma^* L\) by the text so far (Brzozowski 1964). The derivative is a homomorphism of the join-semilattice of sets of words, \(\delta_a(x \vee y) = \delta_a x \vee \delta_a y\), so it is fixed on words and extended to unions; an automaton is the pair \((\varepsilon, \delta)\), a coalgebra on those sets (Rutten 1998).

A state is \(\Sigma^* L \vee S\): a match may still begin anywhere, and the words of S are pending. Every pending word is shorter than the words of L, so none contains one, and S is the state's language less \(\Sigma^* L\): distinct states are distinct languages, and the automaton is minimal by construction (Myhill–Nerode), with no minimisation pass. States are numbered in the order a breadth-first walk finds them, letters in the alphabet's order, so the plan is canonical and == on plans is the equality of the languages they recognise. For one word the plan is Knuth, Morris and Pratt's; Consel and Danvy (1989) obtain it by partially evaluating a naive matcher in the pattern.

The representation is the run list (:runs): the words of length k in the alphabet's order are the chain \([0, \sigma^k)\), a set of them a run list, and the words beginning with a letter one interval, so \(\delta_a\) is a meet with that interval, by the lattice term reducer, then the preimage along a translation. A state is one run list per pending length.

Bounded by its type, on the stack: the states and the steps of their run lists have bounds the caller claims, so the construction runs in the Maybe monad and yields nothing where a claim fails, at either binding time. At compile time a large set may exceed the evaluator's step budget; the same call then runs at run time (#1135).

One function, two binding times

The plan is a value. A constexpr variable forces it at compile time, where a single site's plan (Knuth, Morris and Pratt's) is a constant and a set of 64 sites exceeds the evaluator's budget; the same function builds either at run time, from Python through pynzli. Consel and Danvy (1989) obtain the single-site automaton by partially evaluating a naive matcher in its pattern; here the specialisation is the derivative's.

Wikipedia: Brzozowski derivative, Aho–Corasick algorithm, Knuth–Morris–Pratt algorithm, DFA minimization.

Note: "In this paper the notion of a derivative of a regular expression is introduced and the properties of derivatives are discussed. This leads, in a very natural way, to the construction of a state diagram from a regular expression containing any number of logical operators." – Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM 11(4), 1964, abstract.

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

Function Documentation

◆ derived()

template<std::size_t Sigma, IsCountWord N, std::size_t K>

auto dedekind::category::detail_automaton::derived	(	const RunList< N, K > &	r,
		N	j,
		N	a )

constexpr

Parameters

r	words of length `j`, `j` at least one.
a	a letter.

Returns: \(\delta_a r\): the words of length j - 1 that follow a in them, the meet with a's interval read from its start.

◆ effective_letters()

template<HasNNOStep C, IsArrow F, IsCountWord N>

Letters dedekind::category::detail_automaton::effective_letters ( const Power< C, F, N > & p )

constexpr

Parameters

p a power.

Returns: the letters its words are written in, its slice met with its predicate, as the codes are read; none off the bytes.

◆ kmp_gaattc()

Automaton< 4, 8 > dedekind::category::detail_automaton::kmp_gaattc ( )

constexpr

Returns: KMP's plan for GAATTC, written out: the witness's expectation.

◆ letters_of()

template<HasNNOStep C, IsArrow F, IsCountWord N>

AtMost< C, 257 > dedekind::category::detail_automaton::letters_of ( const Power< C, F, N > & p )

constexpr

Parameters

p a power.

Returns: its letters, in the chain's order: the chain filtered by its predicate, collected, one past the bytes' 256 so that a wider chain is seen as such and refused, not cut to 256.

◆ palindromes()

template<std::size_t KL, std::size_t Sigma, IsCountWord N>

Maybe< RunList< N, KL > > dedekind::category::detail_automaton::palindromes	(	N	n,
		N	prefix,
		N	L )

constexpr

The palindromes of even length n among the codes [prefix, prefix + 1) \(\cdot \sigma^{n - L}\): only their half-sites are visited, none tested.

Parameters

n	the length.
prefix	the code of the `L` letters kept.

Returns: the run list, or nothing where KL is too small or a power outgrows the word.

◆ step()

template<std::size_t Sigma, IsCountWord N, std::size_t P, std::size_t K, std::size_t KL>

Maybe< Residual< N, P, K > > dedekind::category::detail_automaton::step	(	const Residual< N, P, K > &	s,
		const std::array< RunList< N, KL >, Sigma > &	own,
		N	length,
		N	a )

constexpr

Parameters

s	a state.
a	a letter.

Returns: its derivative by a, or nothing where a pending set outgrows its bound.

◆ whole_alphabet()

template<IsCountWord N>

bool dedekind::category::detail_automaton::whole_alphabet ( const Power< std::byte, Letters, N > & p )

constexpr

Parameters

p	a power over the bytes.

Returns: whether its slice holds all its predicate's letters, as the half-site law reads them: a narrower slice has other words and other codes.

Variable Documentation

◆ gaattcgaattc

std::array<std::size_t, 12> dedekind::category::detail_automaton::gaattcgaattc

constexpr

Initial value:

{2, 0, 0, 3, 3, 1,

2, 0, 0, 3, 3, 1}

◆ ttgaattcaagctta

std::array<std::size_t, 15> dedekind::category::detail_automaton::ttgaattcaagctta

constexpr

Initial value:

{3, 3, 2, 0, 0, 3, 3, 1,

0, 0, 2, 1, 3, 3, 0}

Classes

Namespaces

Enumerations

Functions

Variables

Detailed Description

The matcher as a coalgebra

One function, two binding times

Function Documentation

◆ derived()

◆ effective_letters()

◆ kmp_gaattc()

◆ letters_of()

◆ palindromes()

◆ step()

◆ whole_alphabet()

Variable Documentation

◆ gaattcgaattc

◆ ttgaattcaagctta