Finiteness and rational sequences, constructively*. (5th April 2017)

• Record Type: Journal Article
• Authors: UUSTALU, TARMO; VELTRI, NICCOLÒ
• Is Part Of: Journal of functional programming. Volume 27(2017)
• Publication Date: 2017-04-05
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796817000041
• Languages: English
• ISSNs: 0956-7968

Abstract

Abstract: Rational sequences are possibly infinite sequences with a finite number of distinct suffixes. In this paper, we present different implementations of rational sequences in Martin–Löf type theory. First, we literally translate the above definition of rational sequence into the language of type theory, i.e., we construct predicates on possibly infinite sequences expressing the finiteness of the set of suffixes. In type theory, there exist several inequivalent notions of finiteness. We consider two of them, listability and Noetherianness, and show that in the implementation of rational sequences the two notions are interchangeable. Then we introduce the type of lists with backpointers, which is an inductive implementation of rational sequences. Lists with backpointers can be unwound into rational sequences, and rational sequences can be truncated into lists with backpointers. As an example, we see how to convert the fractional representation of a rational number into its decimal representation and vice versa.