(This example is taken from [Tur82] and it was first implemented in the lazy functional programming language Miranda (a trademark of Research Software Ltd.).)
As an example of a program which uses infinite sequences, consider the problem of computing the digits of the transcendental number e. We would like to calculate as many digits of e as we wish. Notice that the decimal expansion of e is an infinite sequence of integers. (Each integer being a single decimal digit.) We could then use in our implementation the infinite sequence datatype which we have just defined.
The number e can be defined as the sum of a series. The terms in the series are the reciprocals of the factorial numbers.
|e||=||1/0! + 1/1! + 1/2! + ...|
|=||2.1111111111111...||(a funny base in which the ith digit has weight 1/i!)|
For any base we have:
Note: The carry factor from the ith digit to the (i-1)th digit is i. I.e. when the ith digit is greater than or equal to i we add 1 to the (i-1)th digit and subtract i from the ith digit.
fun carry(i,cons(x,s))=carry'(i,x,s()) and carry'(i,x,cons(y,s))=cons(x+y div i,lcons(y mod i,s)); fun norm(i,cons(x,s)) ()=norm'(i,x,s()) and norm'(i,x,cons(y,s))=norm''(i,y+9<i,cons(x,norm(i+1,cons(y,s)))) and norm''(i,nocarry,s)=if nocarry then s else carry(i,s); fun normalise s=norm(2,cons(0,tentimes o s)) (); fun convert(cons(x,s)) ()=cons(x,(convert o normalise) s); val e=convert(cons(2,ones));