On lazy natural numbers with applications to computability theory and functional programming
Martı́n Hötzel Escardó · ACM SIGACT News · 1993
Lazy natural numbers arise by lazy evaluation of the successor function. This work investigates fundamental mathematical properties of the domain L of lazy natural numbers, and presents applications to computability theory and functional programming. It is shown that certain functions on sets of natural numbers like cardinality-finding and emptyness-testing which are not continuous (or even monotonic) when sets are given by characteristic functions N⊥ → T are both continuous and computable when sets are given by characteristic functions L → T defined in an appropriate way. These functions are definable in λ calculus based functional programming languages provided some parallel features are available.