1	# Exact rational numbers over BigInt, always in lowest terms.
2	import Base
3	import ./bigint.bend as Big
4	import ./decimal.bend as Dec
5	
6	# num / den with den > 0 and gcd(num, den) = 1, so zero is 0/1 and equal
7	# values are equal terms. Build one with make, from_bigint or from_decimal;
8	# the raw constructor does not normalize.
9	type Rational is Data:
10	  Rational{num: Big.BigInt, den: Big.BigInt}
11	
12	def Rational.low(p: Big.BigInt & Big.BigInt) -> Rational:
13	  (n, d) = p
14	  Rational{n, d}
15	
16	# n / d for a nonzero d.
17	def Rational.norm(n: Big.BigInt, d: Big.BigInt) -> Rational:
18	  Rational.low(Dec.Decimal.lowest(n, d))
19	
20	def Rational.from_bigint(n: Big.BigInt) -> Rational:
21	  Rational{n, Big.BigInt.one()}
22	
23	def Rational.make.if(z: Bool, n: Big.BigInt, d: Big.BigInt) ->
24	  Maybe<&2, Rational>:
25	  match z:
26	    case True{}:
27	      None{}
28	    case False{}:
29	      Some{Rational.norm(n, d)}
30	
31	# n / d in lowest terms, or None when d is zero.
32	def Rational.make(n: Big.BigInt, +d: Big.BigInt) -> Maybe<&2, Rational>:
33	  Rational.make.if(Big.BigInt.is_zero(d), n, d)
34	
35	def Rational.from_decimal(d: Dec.Decimal) -> Rational:
36	  match d:
37	    case Dec.Decimal{u, s}:
38	      Rational.norm(u, Dec.Decimal.pow10(s))
39	
40	# The exact decimal, or None when it repeats (den has a factor besides 2, 5).
41	def Rational.to_decimal(r: Rational) -> Maybe<&2, Dec.Decimal>:
42	  match r:
43	    case Rational{n, d}:
44	      Dec.Decimal.from_fraction(n, d)
45	
46	def Rational.neg(r: Rational) -> Rational:
47	  match r:
48	    case Rational{n, d}:
49	      Rational{Big.BigInt.neg(n), d}
50	
51	def Rational.is_zero(r: Rational) -> Bool:
52	  match r:
53	    case Rational{n, d}:
54	      Big.BigInt.is_zero(n)
55	
56	def Rational.add(a: Rational, b: Rational) -> Rational:
57	  match a b:
58	    case Rational{an, +ad} Rational{bn, +bd}:
59	      Rational.norm(Big.BigInt.add(Big.BigInt.mul(an, bd),
60	        Big.BigInt.mul(bn, ad)), Big.BigInt.mul(ad, bd))
61	
62	def Rational.sub(a: Rational, b: Rational) -> Rational:
63	  Rational.add(a, Rational.neg(b))
64	
65	def Rational.mul(a: Rational, b: Rational) -> Rational:
66	  match a b:
67	    case Rational{an, ad} Rational{bn, bd}:
68	      Rational.norm(Big.BigInt.mul(an, bn), Big.BigInt.mul(ad, bd))
69	
70	# a / b, or None when b is zero.
71	def Rational.div(a: Rational, b: Rational) -> Maybe<&2, Rational>:
72	  match a b:
73	    case Rational{an, ad} Rational{bn, bd}:
74	      Rational.make(Big.BigInt.mul(an, bd), Big.BigInt.mul(ad, bn))
75	
76	# Denominators are positive, so cross-multiplying keeps the order.
77	def Rational.cmp(a: Rational, b: Rational) -> Cmp:
78	  match a b:
79	    case Rational{an, ad} Rational{bn, bd}:
80	      Big.BigInt.cmp(Big.BigInt.mul(an, bd), Big.BigInt.mul(bn, ad))
81	
82	def Rational.show.if(whole: Bool, n: Big.BigInt, d: Big.BigInt) -> String:
83	  match whole:
84	    case True{}:
85	      Big.BigInt.show(n)
86	    case False{}:
87	      Big.BigInt.show(n) ++ "/" ++ Big.BigInt.show(d)
88	
89	# "n/d", or "n" when the denominator is 1.
90	def Rational.show(r: Rational) -> String:
91	  match r:
92	    case Rational{n, +d}:
93	      Rational.show.if(Dec.Decimal.is_one(d), n, d)
94	
95	def Rational.read.frac(a: Maybe<&2, Big.BigInt>, b: Maybe<&2, Big.BigInt>) ->
96	  Maybe<&2, Rational>:
97	  match a b:
98	    case Some{n} Some{d}:
99	      Rational.make(n, d)
100	    case _ _:
101	      None{}
102	
103	def Rational.read.dec(m: Maybe<&2, Dec.Decimal>) -> Maybe<&2, Rational>:
104	  match m:
105	    case Some{d}:
106	      Some{Rational.from_decimal(d)}
107	    case None{}:
108	      None{}
109	
110	def Rational.read.parts(ps: List<&2, String>) -> Maybe<&2, Rational>:
111	  match ps:
112	    case Con{a, Nil{}}:
113	      Rational.read.dec(Dec.Decimal.read(a))
114	    case Con{a, Con{b, Nil{}}}:
115	      Rational.read.frac(Big.BigInt.read(a), Big.BigInt.read(b))
116	    case _:
117	      None{}
118	
119	# "n/d" with BigInt sides (normalized; a zero d is None), or any number
120	# Decimal.read takes, such as "-1.25" or "3e-2".
121	def Rational.read(s: String) -> Maybe<&2, Rational>:
122	  Rational.read.parts(String.split(s, '/'))