The Generic Approximation Lemma
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 generi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Elsevier Science
2001
|
| Online Access: | https://eprints.nottingham.ac.uk/225/ |
| _version_ | 1848790374069305344 |
|---|---|
| author | Hutton, Graham Gibbons, Jeremy |
| author_facet | Hutton, Graham Gibbons, Jeremy |
| author_sort | Hutton, Graham |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:11:36Z |
| format | Article |
| id | nottingham-225 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:11:36Z |
| publishDate | 2001 |
| publisher | Elsevier Science |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-2252020-05-04T20:32:32Z https://eprints.nottingham.ac.uk/225/ The Generic Approximation Lemma Hutton, Graham Gibbons, Jeremy 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. Elsevier Science 2001-08 Article PeerReviewed Hutton, Graham and Gibbons, Jeremy (2001) The Generic Approximation Lemma. Information Processing Letters, 79 (4). pp. 197-201. |
| spellingShingle | Hutton, Graham Gibbons, Jeremy The Generic Approximation Lemma |
| title | The Generic Approximation Lemma |
| title_full | The Generic Approximation Lemma |
| title_fullStr | The Generic Approximation Lemma |
| title_full_unstemmed | The Generic Approximation Lemma |
| title_short | The Generic Approximation Lemma |
| title_sort | generic approximation lemma |
| url | https://eprints.nottingham.ac.uk/225/ |