Recent searches
Search options
#RationalNumbers
Enumerating all of the (positive) #RationalNumbers in 10 lines of #Haskell code.
---------------------------------------------
data Rational = Integer :/ Integer
properFraction :: Rational -> (Integer, Rational)
properFraction (a:/ b) = if a < b then (0, (a :/ b)) else (q, (r :/ b))
where (q, r) = a `quotRem` b
calkinwilfSuccessor :: Rational -> Rational
calkinwilfSuccessor rat = b :/ (b*n + b - a) where (n, (a :/ b)) = properFraction rat
rationals :: [Rational]
rationals = iterate calkinwilfSuccessor (1 :/ 1)
---------------------------------------------
This comes from the 2004 functional pearl paper by Gibbons, Lester and Bird. The main component is a formula credited to Moshe Newman for generating the next element in the Calkin-Wilf sequence (the sequence is simply a breadth-first search enumeration of the Calkin-Wilf tree). See also: https://en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree#Breadth_first_traversal
The Gibbons, Lester, Bird paper contains many other neat pearls involving deforesting trees (Stern-Brocot and Calkin-Wilf trees), the above successor idea, and a continued fraction form which avoids arbitrary-precision integer division (at the cost of a continued fraction representation of the rationals).
Quick note: Generating all rationals using the above is easy. Change to prepend 0, then always produce (𝑥, -𝑥) one after the other with 𝑥 are all positive rationals coming from the above function.
1/5: "Man, I was trying to reason with pi the other day. Cloud't do it."
1/2: "Oh, you can't reason with pi."
1/5: "How come?"
1/2: "Pi is irrational."
