%% Name: ***
%% Date: ***
%% Tabs: ***

Package arithmetic

%% This package provides functions for working with integers,
%% represented as binary lists.
%% 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]
                ;

  dec           : [Bit] -> [Bit]

                %: dec(x) = max(0, x-1), where x and the result are
                %: binary numbers represented as lists.
                ;

  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)
                ;

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

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

  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)
                ;

  compareInts   : ([Bit], [Bit]) -> Char

                %: compareInts(x,y) yields
                %:    '<'  if x < y
                %:    '='  if x = y
                %:    '>'  if x > y
                %: where x and y are binary numbers represented as
                %: lists.  For example, compareInts([0,0,1,1], [0,1,0,1])
                %: yields '>', since 12 > 10.
  
%Expect

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

Import removeTrailing from "collect/list".
Define normalize = removeTrailing 0.

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

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

Define 
  ----------------------------------------------
  %% 0 + 1 = 1

  case incn []       = [1]
  ----------------------------------------------
  %% (2t) + 1 = 2t + 1
   
  case incn (0 :: t) = 1 :: t
  ----------------------------------------------
  %% (2t+1) + 1 = 2(t+1)

  case incn (1 :: t) = 0 :: incn t
  ----------------------------------------------
%Define

Define inc x = normalize(incn x).

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].


%% ***** Write definitions of the remaining functions
%% ***** here and REMOVE THIS COMMENT.

%Package