// file:    a02.rex
// author:  Robert Keller
// purpose: Implement Unicalc in rex

// Problem 1: simplify returns a Quantity equivalent to the argument such
//            that no term appears in both the numerator and denominator.

simplify([F, N, D]) => [F, cancelFrom(N, D), cancelFrom(D, N)];

// Explanation: cancelFrom is used to cancel from the first list
// terms that appear in the second list.  The two uses of cancelFrom
// establish the new numerator and new denominator, respectively.
// The numeric factor is unchanged.


// cancelFrom(L, M) returns the list of items in L but not in M, assuming that
// both lists are sorted.  The result is sorted.

cancelFrom([], M) => [];
cancelFrom(L, []) => L;
cancelFrom([A | L], [A | M]) => cancelFrom(L, M);
cancelFrom([A | L], [B | M]) => A < B ? [A | cancelFrom(L, [B | M])];
cancelFrom([A | L], [B | M]) => cancelFrom([A | L], M);

// Explanation: The fact that both lists are sorted allows us to traverse
// through the two lists only one time.  In the third rule, a common element
// is removed at the head of both lists.  In the fourth rule, if A < B
// then we know that we will never see A in the second list, due to the sorted
// property, so we can include it in the result.  On the other hand,
// if A > B, we know that B will never be seen in the
// first list, so it need not be considered further.

// Note: We cannot simply use 'drop' for cancelFrom, since it may cancel more 
// than one copy of a given uunit.


// Problem 2: multiply multiplies pairs of quantities, producing a simplified
//            result

multiply([M1, N1, D1], [M2, N2, D2]) => 
  simplify([M1*M2, merge(N1, N2), merge(D1, D2)]);
  
// Explanation: This is based on algebra: (N1/D1)*(N2/D2) ==> (N1*N2)/(D1*D2)
// merge is used in multiply to merge the respective numerator and denominator
// lists.  The result is thus guaranteed to be sorted.

  
// divide divides the first quantity by the second, 
// producing a simplified result.

divide([M1, N1, D1], [M2, N2, D2]) => 
  simplify([M1/M2, merge(N1, D2), merge(D1, N2)]);

// Explanation: similar to multiply, but the roles of numerator and
// denominator are applied according to: (N1/D1)/(N2/D2) ==> (N1*D2)/(D1*N2)


// Problem 3:  conv_unit looks up the unit in the database and if found
// returns the second element of the database item, otherwise returns
// the unit in a list by itself with a multiplier of 1 and an empty denom

conv_unit(Unit, DB) =
  Found = assoc(Unit, DB),
  Found == [] ? [1., [Unit], []] // found unit, return created Quantity
              : second(Found);   // return Quantity in database

// The equational guard defining Found means that this value will only be
// computed once.


// Problem 4: norm_unit is like conv_unit but a normalized result is returned.
// Note that norm and norm_unit are mutually recursive.  The basis of
// the mutual recursion lies in the case where Unit is not found.

norm_unit(Unit, DB) =
  Found = assoc(Unit, DB),
  Found == [] ? [1., [Unit], []]         // found unit, return created Quantity
              : norm(second(Found), DB); // return normalized Quantity


// Problem 5:  norm normalizes the lists of numberator and denominator units
// then divides one by the other, finally multiplying in the original factor

norm([M, N, D], DB) => 
  simplify(multiply([M, [], []], 
                    divide(normalizeAll(N, DB), normalizeAll(D, DB))));


// normalizeAll normalizes each unit in a list, then multiplies the results

normalizeAll(L, DB) = multiplyAll(map((X)=>norm_unit(X, DB), L));


// multiplyAll multiplies all quantities in a list together

multiplyAll(L) = reduce(multiply, [1., [], []], L);


// Problem 6:  Converts one Quantity to another.  

convert(A, B, DB) = divide(norm(A, db), norm(B, db));

// Explanation: To convert one Quantity to another, we normalize both
// quantities.  If they are inter-convertible, the resulting numerator and
// denominator will be the same  and the conversion is obtained by dividing
// one numeric factor by the other.  If they are not inter-convertible, then
// the result of division will indicate the residual units in the numerator
// and denominator, respectively.