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

[<EntryPoint>]
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

Raw view Test code New version

More information

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