Professor GRAHAM HUTTON GRAHAM.HUTTON@NOTTINGHAM.AC.UK
PROFESSOR OF COMPUTER SCIENCE
The Generic Approximation Lemma
Hutton, Graham; Gibbons, Jeremy
Authors
Jeremy Gibbons
Abstract
The approximation lemma is a simplification of the well-known take lemma, and is used to prove properties of programs that produce lists of values. We show how the approximation lemma, unlike the take lemma, can naturally be generalised from lists to a large class of datatypes, and present a generic approximation lemma that is parametric in the datatype to which it applies. As a useful by-product, we find that generalising the approximation lemma in this way also simplifies its proof.
Citation
Hutton, G., & Gibbons, J. (2001). The Generic Approximation Lemma. Information Processing Letters, 79(4), https://doi.org/10.1016/S0020-0190%2800%2900220-9
Journal Article Type | Article |
---|---|
Publication Date | Aug 1, 2001 |
Deposit Date | Oct 26, 2005 |
Publicly Available Date | Oct 9, 2007 |
Journal | Information Processing Letters |
Print ISSN | 0020-0190 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 79 |
Issue | 4 |
DOI | https://doi.org/10.1016/S0020-0190%2800%2900220-9 |
Public URL | https://nottingham-repository.worktribe.com/output/1023047 |
Files
approx.pdf
(107 Kb)
PDF
You might also like
Quotient Haskell: Lightweight Quotient Types for All
(2024)
Journal Article
Programming language semantics: It’s easy as 1,2,3
(2023)
Journal Article
Monadic compiler calculation (functional pearl)
(2022)
Journal Article
Calculating dependently-typed compilers (functional pearl)
(2021)
Journal Article
Calculating correct compilers II: Return of the register machines
(2020)
Journal Article
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2025
Advanced Search