A completely unique account of enumeration

Cas van der Rest; Wouter Swierstra

doi:10.1145/3547636

A completely unique account of enumeration

Cas van der Rest, Wouter Swierstra

Delft University of Technology

Research output: Contribution to journal › Conference article › Academic › peer-review

Abstract

How can we enumerate the inhabitants of an algebraic datatype? This paper explores a datatype generic solution that works for all regular types and indexed families. The enumerators presented here are provably both complete and unique—they will eventually produce every value exactly once—and fair—they avoid bias when composing enumerators. Finally, these enumerators memoise previously enumerated values whenever possible, thereby avoiding repeatedly recomputing recursive results.

Original language	English
Article number	105
Pages (from-to)	411–437
Journal	Proceedings of the ACM on Programming Languages
Volume	6
DOIs	https://doi.org/10.1145/3547636
Publication status	Published - 2022

Access to Document

10.1145/3547636Licence: CC BY

3547636Final published version, 291 KBLicence: CC BY

Cite this

@article{d627f914cb1e47f9a0a56df75e6adc35,

title = "A completely unique account of enumeration",

abstract = "How can we enumerate the inhabitants of an algebraic datatype? This paper explores a datatype generic solution that works for all regular types and indexed families. The enumerators presented here are provably both complete and unique—they will eventually produce every value exactly once—and fair—they avoid bias when composing enumerators. Finally, these enumerators memoise previously enumerated values whenever possible, thereby avoiding repeatedly recomputing recursive results.",

author = "{van der Rest}, Cas and Wouter Swierstra",

year = "2022",

doi = "10.1145/3547636",

language = "English",

volume = "6",

pages = "411–437",

journal = "Proceedings of the ACM on Programming Languages",

issn = "2475-1421",

publisher = "Association for Computing Machinery",

}

TY - JOUR

T1 - A completely unique account of enumeration

AU - van der Rest, Cas

AU - Swierstra, Wouter

PY - 2022

Y1 - 2022

N2 - How can we enumerate the inhabitants of an algebraic datatype? This paper explores a datatype generic solution that works for all regular types and indexed families. The enumerators presented here are provably both complete and unique—they will eventually produce every value exactly once—and fair—they avoid bias when composing enumerators. Finally, these enumerators memoise previously enumerated values whenever possible, thereby avoiding repeatedly recomputing recursive results.

AB - How can we enumerate the inhabitants of an algebraic datatype? This paper explores a datatype generic solution that works for all regular types and indexed families. The enumerators presented here are provably both complete and unique—they will eventually produce every value exactly once—and fair—they avoid bias when composing enumerators. Finally, these enumerators memoise previously enumerated values whenever possible, thereby avoiding repeatedly recomputing recursive results.

U2 - 10.1145/3547636

DO - 10.1145/3547636

M3 - Conference article

SN - 2475-1421

VL - 6

SP - 411

EP - 437

JO - Proceedings of the ACM on Programming Languages

JF - Proceedings of the ACM on Programming Languages

M1 - 105

ER -

A completely unique account of enumeration

Abstract

Access to Document

Fingerprint

Cite this