Package arithmetic

%% This package provides functions for incrementing,
%% adding and multiplying binary numbers, represented as lists.
%%
%% In all cases, lists begin with the low order end of the number.
%% For example, list [1,1,0,0,1] stands for the binary number
%% 10011, or 19 in decimal.
%%
%% A list is normalized if it does not end on 0.  All of the
%% following functions produce normalized results, even if the
%% parameter(s) are not normalized.

================================================================
                        export
================================================================

Abbrev Bit = Integer.

Expect
  inc		: [Bit] -> [Bit]

		%: inc(x) is x+1, where both x and the result are binary
		%: numbers represented as lists.
		%: For example inc([1,0,1,1]) = [0,1,1,1]
		;

  sum		:  ([Bit], [Bit]) -> [Bit]

		%: sum(x,y) = x + y, where x, y and the result are
		%: binary numbers represented as lists.  For example,
		%: sum([0,1,1], [1,1,1]) = [1,0,1,1].  (6 + 7 = 13)
		;

  product	: ([Bit], [Bit]) -> [Bit]

		%: product(x,y) = x * y, where x, y and the result are
		%: binary numbers represented as lists.  For example,
		%: product([1,1], [1,1]) = [1,0,0,1].  (3*3 = 9)
		;
		
%Expect

================================================================
                        implementation
================================================================

Import "collect/list".  %% Provides removeTrailing.

Define normalize = removeTrailing 0.

===============================================================
%%                    inc
===============================================================

%% incNN is similar to inc, but does not normalize its result.
%% (NN stands for non-normalizing)

Team
  Example incNN [1,1,0,1,1] = [0,0,1,1,1].
  Example incNN [1]         = [0,1].

  Define 
    case incNN []       = [1]
    case incNN (0 :: t) = 1 :: t
    case incNN (1 :: t) = 0 :: incNN t
  %Define

  Example inc [1,1,0,1,1,0,0] = [0,0,1,1,1].
  Example inc [1] = [0,1].
  Example inc [1,0,0] = [0,1].

  Define inc x = normalize(incNN x).
%Team

%% ***** Write definitions of sum and product here,
%% ***** and remove this comment.

%Package