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 = Natural.

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/listfun".  %% Provides removeTrailing.

Define normalize = removeTrailing 0.

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

%% inc_a is similar to inc, but does not normalize its result.

Define 
  Example inc_a [1,1,0,1,1] = [0,0,1,1,1].
  Example inc_a [1]         = [0,1].

  case inc_a [] = [1]
  case inc_a (0::?t) = 1::t
  case inc_a (1::?t) = 0::inc t
%Define

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

  inc ?x = normalize(inc_a x)
%Define



%% ***** Write your function definitions in this part, and remove this comment.

%Package