4 people like it.

# Enumerating the Rationals

How to enumerate the rational numbers without duplication using a Calkinâ€“Wilf tree.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: ``` ``````open System.Numerics // http://fsharpnews.blogspot.com/2013/08/implementing-rationals-in-f.html type Rational(p: BigInteger, q: BigInteger) = let rec gcd a (b: BigInteger) = if b.IsZero then a else gcd b (a % b) let fixSign(p: BigInteger, q: BigInteger) = if q.Sign > 0 then p, q else -p, -q let p, q = if q.IsZero then raise(System.DivideByZeroException()) let g = gcd q p fixSign(p/g, q/g) member __.Numerator = p member __.Denominator = q override __.ToString() = if q.IsOne then p.ToString() else sprintf "%A/%A" p q static member (+) (m: Rational, n: Rational) = Rational(m.Numerator*n.Denominator + n.Numerator*m.Denominator, m.Denominator*n.Denominator) static member (-) (m: Rational, n: Rational) = Rational(m.Numerator*n.Denominator - n.Numerator*m.Denominator, m.Denominator*n.Denominator) static member (*) (m: Rational, n: Rational) = Rational(m.Numerator*n.Numerator, m.Denominator*n.Denominator) static member (/) (m: Rational, n: Rational) = Rational(m.Numerator*n.Denominator, m.Denominator*n.Numerator) let recip (r : Rational) = Rational(r.Denominator, r.Numerator) let fromInteger n = Rational(n, 1I) let properFraction (r : Rational) = let whole = r.Numerator / r.Denominator let part = Rational(r.Numerator % r.Denominator, r.Denominator) whole, part let one = fromInteger 1I let iterate f x = let rec loop x = seq { yield x yield! loop (f x) } loop x /// https://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf let next x = let n, y = properFraction x recip (fromInteger n + one - y) let rationals = iterate next one [] let main argv = for r in rationals do printfn "%A" r 0 ``````
namespace System
namespace System.Numerics
Multiple items
type Rational =
new : p:BigInteger * q:BigInteger -> Rational
override ToString : unit -> string
member Denominator : BigInteger
member Numerator : BigInteger
static member ( + ) : m:Rational * n:Rational -> Rational
static member ( / ) : m:Rational * n:Rational -> Rational
static member ( * ) : m:Rational * n:Rational -> Rational
static member ( - ) : m:Rational * n:Rational -> Rational

Full name: Script.Rational

--------------------
new : p:BigInteger * q:BigInteger -> Rational
val p : BigInteger
Multiple items
type BigInteger =
struct
new : value:int -> BigInteger + 7 overloads
member CompareTo : other:int64 -> int + 3 overloads
member Equals : obj:obj -> bool + 3 overloads
member GetHashCode : unit -> int
member IsEven : bool
member IsOne : bool
member IsPowerOfTwo : bool
member IsZero : bool
member Sign : int
member ToByteArray : unit -> byte[]
...
end

Full name: System.Numerics.BigInteger

--------------------
BigInteger()
BigInteger(value: int) : unit
BigInteger(value: uint32) : unit
BigInteger(value: int64) : unit
BigInteger(value: uint64) : unit
BigInteger(value: float32) : unit
BigInteger(value: float) : unit
BigInteger(value: decimal) : unit
BigInteger(value: byte []) : unit
val q : BigInteger
val gcd : (BigInteger -> BigInteger -> BigInteger)
val a : BigInteger
val b : BigInteger
property BigInteger.IsZero: bool
val fixSign : (BigInteger * BigInteger -> BigInteger * BigInteger)
property BigInteger.Sign: int
val raise : exn:System.Exception -> 'T

Full name: Microsoft.FSharp.Core.Operators.raise
Multiple items
type DivideByZeroException =
inherit ArithmeticException
new : unit -> DivideByZeroException + 2 overloads

Full name: System.DivideByZeroException

--------------------
System.DivideByZeroException() : unit
System.DivideByZeroException(message: string) : unit
System.DivideByZeroException(message: string, innerException: exn) : unit
val g : BigInteger
member Rational.Numerator : BigInteger

Full name: Script.Rational.Numerator
val __ : Rational
member Rational.Denominator : BigInteger

Full name: Script.Rational.Denominator
override Rational.ToString : unit -> string

Full name: Script.Rational.ToString
property BigInteger.IsOne: bool
BigInteger.ToString() : string
BigInteger.ToString(format: string) : string
BigInteger.ToString(provider: System.IFormatProvider) : string
BigInteger.ToString(format: string, provider: System.IFormatProvider) : string
val sprintf : format:Printf.StringFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.sprintf
val m : Rational
val n : Rational
property Rational.Numerator: BigInteger
property Rational.Denominator: BigInteger
val recip : r:Rational -> Rational

Full name: Script.recip
val r : Rational
val fromInteger : n:BigInteger -> Rational

Full name: Script.fromInteger
val n : BigInteger
val properFraction : r:Rational -> BigInteger * Rational

Full name: Script.properFraction
val whole : BigInteger
val part : Rational
val one : Rational

Full name: Script.one
val iterate : f:('a -> 'a) -> x:'a -> seq<'a>

Full name: Script.iterate
val f : ('a -> 'a)
val x : 'a
val loop : ('a -> seq<'a>)
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val next : x:Rational -> Rational

Full name: Script.next

https://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf
val x : Rational
val y : Rational
val rationals : seq<Rational>

Full name: Script.rationals
Multiple items
type EntryPointAttribute =
inherit Attribute
new : unit -> EntryPointAttribute

Full name: Microsoft.FSharp.Core.EntryPointAttribute

--------------------
new : unit -> EntryPointAttribute
val main : argv:string [] -> int

Full name: Script.main
val argv : string []
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

### More information

 Link: http://fssnip.net/7VB Posted: 2 months ago Author: Brian Berns Tags: gcd , numbers , rational