From: Jonathan Aldrich <jonal@ozette.cs.washington.edu>
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.