fold.cppm File Reference

The left fold (catamorphism) over an enumerable sequence. More...

#include <algorithm>
#include <utility>

Include dependency graph for fold.cppm:

Functions
template<typename Range, typename Acc, typename Op>
constexpr Acc	dedekind::sequences::fold (const Range &xs, Acc acc, Op op)
	Strict left fold over an enumerable range xs.

Detailed Description

The left fold (catamorphism) over an enumerable sequence.

@partition :fold

Copyright

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

fold__Overview

fold(xs, init, op) reduces a sequence to a single value by threading an accumulator, op(acc, x) left to right. It is the point-free primitive behind the graph closure of dedekind.optimization:closure — a graph algorithm becomes a fold over its edge sequence rather than nested index loops. A fold is defined only for an enumerable (extensional) sequence: an intensional predicate has no elements to thread (Rice), so its relation is materialised extensionally first, then folded.

Function Documentation

fold()

template<typename Range, typename Acc, typename Op>

Acc dedekind::sequences::fold ( const Range & xs, Acc acc, Op op )

constexprexport

Strict left fold over an enumerable range xs.

Threads the accumulator through op(acc, x) left to right and returns it. A scalar accumulator recovers the familiar reduction (sum, product); a structured accumulator (a potential vector) a stateful pass.

The step is a function of the accumulator and the element, acc = op(acc, x): the textbook \(\mathrm{fold}(\oplus, e)\), with no effect on anything but its result. The accumulator is moved into the step and moved out, so a cheaply movable accumulator costs nothing per step; a fixed-capacity array (the closure's potential net) is copied by its move, which is the honest price of a fold that is a fold.

Parameters

xs	any range with begin / end (e.g. a constexpr array, which folds to a constant at translation time).
acc	the seed accumulator (returned, threaded).
op	op(acc, x): the new accumulator, applied left to right.