# Shades of Iteration: from Elgot to Kleene

arXiv: https://arxiv.org/abs/2301.06202 · HTML: https://mlsanity.com/paper/2301.06202/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 47 references that are in the map.
- First posted on arXiv 15 Jan 2023.

## Builds on (most cited first, 6 of 6)

- [Denotational Correctness of Forward-Mode Automatic Differentiation for Iteration and Recursion](https://mlsanity.com/paper/2007.05282/) (2020)
- [Unguarded Recursion on Coinductive Resumptions](https://mlsanity.com/paper/1405.0854/) (2014)
- [Some Remarks on Conway and Iteration Theories](https://mlsanity.com/paper/1603.00838/) (2016)
- [Guarded Traced Categories](https://mlsanity.com/paper/1802.08756/) (2018)
- [A Semantics for Hybrid Iteration](https://mlsanity.com/paper/1807.01053/) (2018)
- [Uniform Elgot Iteration in Foundations](https://mlsanity.com/paper/2102.11828/) (2021)

## Abstract (arXiv)

Notions of iteration range from the arguably most general Elgot iteration to a very specific Kleene iteration. The fundamental nature of Elgot iteration has been extensively explored by Bloom and Esik in the form of iteration theories, while Kleene iteration became extremely popular as an integral part of (untyped) formalisms, such as automata theory, regular expressions and Kleene algebra. Here, we establish a formal connection between Elgot iteration and Kleene iteration in the form of Elgot monads and Kleene monads, respectively. We also introduce a novel class of while-monads, which like Kleene monads admit a relatively simple description in algebraic terms. Like Elgot monads, while-monads cover a large variety of models that meaningfully support while-loops, but may fail the Kleene algebra laws, or even fail to support a Kleen iteration operator altogether.