From: Jonathan Aldrich Subject: Infinite data structure example My idea was not nearly so creative as Dan's Turing machine, but you are welcome to use it if you'd like. As stated on my homework, it computes successive approximations to Pi using an algorithm that converges quadratically. 2) This Haskell code computes a series of successive approximations to Pi. The series converges quadratically; that is, the number of significant digits doubles from one element of the series to the next. As you will see, this very quickly exhausts the precision of Haskell floating point numbers. I used a series documented in a recent Scientific American article, and described in detail at http://pw1.netcom.com/~hjsmith/Pi/PiWhy.html. The following pseudocode should make the algorithm clear: y = sqrt(0.5) x = 0.5 for i = 1 to n do y = (1 - sqrt(1 - square(y))) / (1 + sqrt(1 - square(y))) x = square(1 + y) * x - 2^n * y pi = 1/x done Here is the Haskell code that defines a series piapprox (along with a couple of "helper series") that converges using this algorithm. All three series are infinite: -- helper square function square x = x * x -- sy represents successive y values in the pseudocode above. It -- starts out being sqrt(0.5) and is recursively calculated. sy = (sqrt 0.5) : syrest sy where syrest (y:ys) = (1 - sqrt(1 - square y))/(1 + sqrt(1 - square y)) : syrest ys -- sx represents successive x values in the pseudocode above. It -- starts out being 0.5 and is recursively calculated from there. sx = 0.5 : sxrest sx (tail sy) 2 where sxrest (x:xs) (y:ys) n2 = (square (1+y) * x) - n2 * y : sxrest xs ys (n2*2) -- the nth element of piapprox is 1/x[n] piapprox = extractpi sx where extractpi (x:xs) = (1/x) : extractpi xs We can test the code by taking the first 10 members of the series: take 10 piapprox [2.0, 2.91421, 3.14058, 3.14159, 3.14159, 3.14159, 3.14159, 3.14159, 3.14159, 3.14159] As you can see, in only 4 steps we have approximated pi to 5 decimal places.