A tutorial on the universality and expressiveness of fold¶
HUTTON, G. (1999). A tutorial on the universality and expressiveness of fold. Journal of Functional Programming, 9(4), 355-372.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Identity Element
- A two-sided identity turns the question into a lookup — the empty composition has a value, and that value is e — so absence enters the model as data rather than as a control-flow event.
This sourceShows that the seed argument of a fold supplies the value for the empty input, so base cases and emptiness tests need not be written separately from the step.
Supported in partVerified against the publisher's abstract
Hutton's tutorial backs only the list-fold strand of this claim — fold's universal property and seed absorb the empty case — and says nothing about accumulators, batches, partitions, windows, shards or tenants.
“we emphasize the use of the universal property of fold both as a proof principle that avoids the need for inductive proofs, and as a definition principle that guides the transformation of recursive functions into definitions using fold.”
- A two-sided identity turns the question into a lookup — the empty composition has a value, and that value is e — so absence enters the model as data rather than as a control-flow event.
Domain-specific¶
- Universal property
- That unique map is exactly
foldr: given a seed and a combiner, there is one and only one homomorphism, which is whyfoldris uniquely determined and why the "fold-fusion" laws used to optimize and derive programs are validThis sourceThe universal property of fold, that fold f v is the unique function satisfying its defining equations, and the derivation of the fusion law from it.
SupportedVerified against the source
- That unique map is exactly
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 2 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:5483116de319 · see in the full table