On Thu, 10 Oct 2002, Jerzy Karczmarczuk wrote:
Ashley Yakeley wrote:
I considered doing something very like this for real (computable) numbers, but because I couldn't properly make the type an instance of Eq, I left it. Actually it was worse than that. Suppose I'm adding two numbers, both of which are actually 1, but I don't know that:
1.000000000.... + 0.999999999....
The trouble is, as far as I know with a finite number of digits, the answer might be 1.9999999999937425 or it might be 2.0000000000013565
...so I can't actually generate any digits at all. So I can't even make the type an instance of my Additive class.
You can, unless you are so ambitious that you want to have an ideal solution. Doing the stuff lazily means that you will have a thunk used in further computations, and the digits will be generated according to your needs.
You *MAY* generate these digits physically ('1' or '2' in your case) if you permit yourself to engage in a possibly bottom-less recursive pit, which in most interesting cases actually *has* a bottom, and the process stops. Please look my "Pi" crazy essay. Once the decision concerning the carry is taken, the process becomes "sane", generative, co-recursive, until the next ambiguity.
There are of course more serious approaches: intervals, etc. The infinite- precision arithmetic is a mature domain, developed by many people. Actually the Gosper arithmetic of continued fractions is also based on co-recursive expansion, although I have never seen anybody implementing it using a lazy language, and a lazy protocol.
I submitted a paper to JFP about lazy continued fractions in about 1997, but got side-tracked into answering the reviewers' comments. It _is_ possible to do continued fractions lazily, but proving that it's correct involves a proof with several thousand cases. A discussion of that proof can be found in "15th IEEE Symposium on Computer Arithmetic, Vail 2001". I ought to get around to a journal publication someday. David Lester.
Anybody wants to do it with me? (Serious offers only...)
Jerzy Karczmarczuk _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe