for review: big rats
Bert Thompson
aet at hydra.cs.mu.oz.au
Thu Apr 9 16:03:48 AEST 1998
Fergus Henderson <fjh at cs.mu.OZ.AU> writes:
Fergus,
Thanks for the suggestions. I've made the changes, with one remark below.
|The way to defining equality for a type is with `where equality is <blah>'
|in the type declaration, rather than by defining an =/2 predicate.
|It's probably a bug if the compiler does not at least warn you
|if you try to do that.
|In this case, the builtin unification will do the correct thing, so you
|can just delete this predicate. However, a comment next to the type
|definition about the type's invariant and why it is needed (to ensure
|that the builtin equality gives correct results) would be a good idea.
I've done this, but I think adding the `where equality is <blah>'
approach may be preferable since it makes the code blindingly obvious:
it does what it says not what the comments say.
(Who has any faith in comments?)
Anyway, here's the diff...
------------------------------------------------------------
*** 1.4 1998/04/08 07:36:14
--- rational.m 1998/04/09 06:02:59
***************
*** 68,73 ****
--- 68,89 ----
:- import_module require.
+ % The normal form of a rational number has the following
+ % properties:
+ % - numerator and denominator have no common factors.
+ % - denominator is positive.
+ % - denominator is not zero.
+ % - if numerator is zero, then denominator is one.
+ %
+ % These invariants must be preserved by any rational number
+ % constructed using this module since the equality predicate
+ % on rationals is simply Mercury's default unification
+ % predicate =/2. If the invariants were not maintained,
+ % we would have pathologies like r(-1,2) \= r(1,-2).
+ %
+ % The rational_norm/2 predicate generates rationals in this
+ % normal form.
+ %
:- type rational
---> r(integer, integer).
***************
*** 79,99 ****
rational:'=<'(R1, R2) :-
Cmp = cmp(R1, R2),
! (Cmp = lessthan; Cmp = equal).
rational:'>='(R1, R2) :-
Cmp = cmp(R1, R2),
! (Cmp = greaterthan; Cmp = equal).
!
! rational(Num, Den) = rational_norm(r(integer(Num), integer(Den))).
! rational_from_integers(Num, Den) = rational_norm(r(Num, Den)).
! % We needn't call rational_norm since rationals can be
! % created only by the rational constructors or by rational
! % operations, the results of which must be normalised.
! rational:'='(r(An, Ad), r(Bn, Bd)) :-
! An = Bn, Ad = Bd.
%% XXX: There are ways to do this in some cases even if the
%% float conversions would overflow.
--- 95,109 ----
rational:'=<'(R1, R2) :-
Cmp = cmp(R1, R2),
! (Cmp = lessthan ; Cmp = equal).
rational:'>='(R1, R2) :-
Cmp = cmp(R1, R2),
! (Cmp = greaterthan ; Cmp = equal).
! rational(Num, Den) = rational_norm(integer(Num), integer(Den)).
! rational_from_integers(Num, Den) = rational_norm(Num, Den).
%% XXX: There are ways to do this in some cases even if the
%% float conversions would overflow.
***************
*** 109,116 ****
rational:'-'(r(Num, Den)) = r(-Num, Den).
rational:'+'(r(An, Ad), r(Bn, Bd)) =
! rational_norm(r(An*CA + Bn*CB, M)) :-
! M = lcm(Ad,Bd),
CA = M / Ad,
CB = M / Bd.
--- 119,126 ----
rational:'-'(r(Num, Den)) = r(-Num, Den).
rational:'+'(r(An, Ad), r(Bn, Bd)) =
! rational_norm(An*CA + Bn*CB, M) :-
! M = lcm(Ad, Bd),
CA = M / Ad,
CB = M / Bd.
***************
*** 119,127 ****
rational:'*'(r(An, Ad), r(Bn, Bd)) =
% XXX: need we call rational_norm here?
! rational_norm(r((An//G1)*(Bn//G2), (Ad//G2)*(Bd//G1))) :-
! G1 = gcd(An,Bd),
! G2 = gcd(Ad,Bn).
rational:'/'(R1, R2) =
R1 * inverse(R2).
--- 129,137 ----
rational:'*'(r(An, Ad), r(Bn, Bd)) =
% XXX: need we call rational_norm here?
! rational_norm((An//G1)*(Bn//G2), (Ad//G2)*(Bd//G1)) :-
! G1 = gcd(An, Bd),
! G2 = gcd(Ad, Bn).
rational:'/'(R1, R2) =
R1 * inverse(R2).
***************
*** 128,137 ****
:- func inverse(rational) = rational.
inverse(r(Num, Den)) = Rat :-
! (Num = izero ->
error("rational:inverse: division by zero")
;
! Rat = r(signum(Num)*Den,abs(Num))
).
rational:numer(r(Num, _)) = Num.
--- 138,147 ----
:- func inverse(rational) = rational.
inverse(r(Num, Den)) = Rat :-
! ( Num = izero ->
error("rational:inverse: division by zero")
;
! Rat = r(signum(Num)*Den, abs(Num))
).
rational:numer(r(Num, _)) = Num.
***************
*** 138,162 ****
rational:denom(r(_, Den)) = Den.
! rational:abs(r(Num,Den)) = r(abs(Num),Den).
! % The normal form of a rational number has the following
! % properties:
! % - numerator and denominator have no common factors.
! % - denominator is positive.
! % - denominator is not zero.
! % - if numerator is zero, then denominator is one.
! :- func rational_norm(rational) = rational.
! rational_norm(r(Num, Den)) = Rat :-
( Den = izero ->
! error("rational_norm: division by zero")
; Num = izero ->
! Rat = r(izero,ione)
;
Rat = r(Num2//G, Den2//G),
Num2 = Num * signum(Den),
Den2 = abs(Den),
! G = gcd(Num,Den)
).
:- func gcd(integer, integer) = integer.
--- 148,166 ----
rational:denom(r(_, Den)) = Den.
! rational:abs(r(Num, Den)) = r(abs(Num), Den).
! :- func rational_norm(integer, integer) = rational.
! rational_norm(Num, Den) = Rat :-
( Den = izero ->
! error("rational:rational_norm: division by zero")
; Num = izero ->
! Rat = r(izero, ione)
;
Rat = r(Num2//G, Den2//G),
Num2 = Num * signum(Den),
Den2 = abs(Den),
! G = gcd(Num, Den)
).
:- func gcd(integer, integer) = integer.
***************
*** 207,217 ****
:- pred is_zero(rational).
:- mode is_zero(in) is semidet.
! is_zero(r(Num,_)) :-
Num = izero.
:- pred is_negative(rational).
:- mode is_negative(in) is semidet.
! is_negative(r(Num,_)) :-
Num < izero.
--- 211,221 ----
:- pred is_zero(rational).
:- mode is_zero(in) is semidet.
! is_zero(r(Num, _)) :-
Num = izero.
:- pred is_negative(rational).
:- mode is_negative(in) is semidet.
! is_negative(r(Num, _)) :-
Num < izero.
More information about the developers
mailing list