Continued Fractions in Haskell
cdsmithus.medium.com
cdsmithus.medium.com
One thing to watch out for is that when you compute floor(sqrt(2) * sqrt(2)), the computation will never finish. The reason is that continued fractions only compute approximations, so the approximation will only tell you that the result is very close to 2, but it might still be slightly above or below 2. That is, unless you implement some logic to deal with repeating coefficients, but then you will have the same problem with 1/pi times pi, for example.
This is a fundamental problem shared by any form of exact real arithmetic with unique representations; you can always then be forced to make a choice, before emitting any information, that depends on infinite amounts of information about the operands. To solve this problem, you would need to choose a representation with redundancy. (With redundancy, equality comparison becomes harder, and it can still diverge, but you can still get approximations of the answer.)
With the decimal and continued fraction representations, that's not true. The later parts of the representations only describe refinements on the earlier parts; they don't themselves contain the earlier parts.
> In a sense, every single one of the rational numbers in that sequence is useles.
"Every single one" is not the same as "all".
But it's not quite right, as you note. Better to say "every single one is mostly redundant information"
Pick a, b such that x^2 > a and b=x^2 - a. Then there is a continued fraction of the form:
x = a + b/(2a + b/(2a + \dots)).
The other way to find the sqrt is with Newton's method. The rationals given by Newton appear in the list generated by the partial fraction (convergents).
The first step in the completion is going to involve a tangent space, which I think looks a bit like the first step in Newton. I think the idea with storing information in a "continued fraction" form could then be generalised a bit. It probably applies to more things than just irrationals.
The fact there are multiple continued fractions for real numbers is okay because it is a quotient, you have picked a representative.
Impressive the very simple representations of sqrt of 2, sqrt of 3 and sqrt of 5.
pi = 3 + (1^2)/6 + (3^2)/6 + (5^2)/6 + (7^2)/6 + (9^2)/6 + (11^2)/6 + ...
(These were later edits to the article, so if you read it early on, you may not have read those parts.)
[1]: https://golem.ph.utexas.edu/category/2020/08/eulers_continue...
Mutable arrays, for the clever people who know how or print.
Also, looking at the article, the cryptic "fix" operator for making a cyclic structure. Elegant, beautiful, efficient, but mysterious.
print “hello world”
let one_zeros = 1 : zero_ones
zero_ones = 0 : one_zerosAnyway here's one from Data.Functor.Foldable.Exotic just for fun:
anaM :: (Corecursive t, Traversable (Base t), Monad m) => (a -> m (Base t a)) -> (a -> m t)
anaM psi = a where a = (fmap embed . traverse a) <=< psi