% NOTE : The percent character '%' begins a comment line.


STRUCTURE zero:number 
          succ(pred:number):number.


%STRUCTURE Atomic(index:number):wff
%          Negation(not:wff):wff
%          Conjunction(leftand:wff,rightand:wff):wff
%          Disjunction(leftor:wff,rightor:wff):wff.
          


STRUCTURE empty:list 
          add(head:number,tail:list):list.


STRUCTURE True:boolean 
          False:boolean.





%***********************************************************************
FUNCTION  Plus(x,y:Number):Number; % Binary addition.
BEGIN
if (y = zero) Then x;  

if (y != zero) Then succ(plus(x,pred(y)));
END.
%***********************************************************************


%***********************************************************************
FUNCTION Times(x,y:number):number;
BEGIN
if (x = zero) Then zero; 
if (x != zero) Then plus(y,times(pred(x),y));
END.
%***********************************************************************



FUNCTION Fact(x:number):number;
BEGIN
if x = zero Then succ(zero);
if x != zero Then times(x,fact(pred(x)));
END.


FUNCTION Fibonacci(x:number):number;
BEGIN
If x = zero Then zero;

If (x = succ(zero)) Then succ(zero);

If ((x != zero) And (x != succ(zero))) Then Plus(Fibonacci(pred(x)),
                                                 Fibonacci(pred(pred(x))));

END.

FUNCTION Less(x,y:number):Boolean;
BEGIN
if ( (x = zero) And (y = zero) )   Then False;
if ( (x = zero) And (y != zero) )  Then True;
if ( (x != zero) And (y = zero) )  Then False;
if ( (x != zero) And (y != zero) ) Then Less(pred(x),pred(y));
END.


FUNCTION Equal(x,y:number):Boolean;
BEGIN
if ( (x = zero) And (y = zero) )   Then True;
if ( (x = zero) And (y != zero) )  Then False;
if ( (x != zero) And (y = zero) )  Then False;
if ( (x != zero) And (y != zero) ) Then Equal(pred(x),pred(y));
END.


FUNCTION Leq(x,y:number):Boolean;
BEGIN
if ( (Less(x,y) = True) Or (Equal(x,y) = True) ) Then True;
if ( (Less(x,y) != True) And (Equal(x,y) != True) ) Then False;
END.


FUNCTION Minus(x,y:number):number;
BEGIN
If [ (x = zero) Or (y = zero) ] Then x;
If [ (x != zero) And (y != zero) ] Then Minus(pred(x),pred(y));
END.


FUNCTION Minus1(x,y:number):number;
BEGIN
if (y = zero) Then x;
if (y != zero) Then pred(Minus1(x,pred(y)));
END.


FUNCTION Minus2(n,m:number):number;
BEGIN
if (m = zero) then n;
if (m != zero) Then Minus2(pred(n),pred(m));
END.

FUNCTION Concat(x,y:list):list;
BEGIN
if (x = empty) Then y;
if [ (x != empty) And (tail(x) = empty) ] Then add(head(x),y);
if [(x != empty) And (tail(x) != empty)] Then add(head(x),Concat(Tail(x),y));
END.


FUNCTION Reverse(x:list):list;
BEGIN
if (x = empty) Then x;
if ( (x != empty) And (tail(x) = empty)  ) Then x;
if ( (x != empty) And (tail(x) != empty) ) Then 
                                 Concat(Reverse(tail(x)),add(head(x),empty));
END.


FUNCTION Remove(n:number,x:list):list;
BEGIN
If x = empty then x;
if ( (x != empty) And (Equal(head(x),n) = True) )  Then Remove(n,tail(x));
if ( (x != empty) And (Equal(head(x),n) = False) ) 
      Then add(head(x),Remove(n,tail(x)));
END.


FUNCTION half(x:number):number;
BEGIN
If (pred(x) = zero) then zero;
If (pred(x) != zero) then succ(half(pred(pred(x))));
End.


FUNCTION Minimum(x:list):number;
BEGIN

If (x = empty) then zero;

If ( (x = add(head(x),tail(x))) And (tail(x) = empty) ) Then head(x);

If [(x = add(head(x),tail(x))) And (tail(x) = add(head(tail(x)),tail(tail(x))))
    And (Less(head(tail(x)),head(x)) = True) ]  Then Minimum(tail(x));

If [(x = add(head(x),tail(x))) And (tail(x) = add(head(tail(x)),tail(tail(x))))
    And (Less(head(tail(x)),head(x)) = False) ]  
    Then Minimum(add(head(x),tail(tail(x))));

END.


Function Member(n:number,x:list):Boolean;
BEGIN
If (x = empty) then False;

If [ (x != empty) And (Equal(n,head(x)) = True) ] Then True;

If [ (x != empty) And (Equal(n,head(x)) = False) ] Then Member(n,tail(x));
END.


Function Max(x,y:number):number;
BEGIN
if Leq(x,y) = True  Then y;
if Leq(x,y) = False Then x;
END.


Function GCD(x,y:number):number;
BEGIN
If [ (x = zero) Or (y = zero) ] Then Max(x,y);
if [ (x != zero) And (y != zero) And (Leq(x,y) = True) ] Then GCD(x,Minus(y,x));
if [ (x != zero) And (y != zero) And (Leq(x,y) = False) ] Then GCD(Minus(x,y),y);
END.


Function Log(n:number):number;
BEGIN
If (n = zero) Then zero;

If [ (n = succ(pred(n))) And (pred(n) = zero) ] Then zero;

If [ (n = succ(pred(n))) And (pred(n) = succ(pred(pred(n)))) ] Then succ(Log(Half(n)));
END.


FUNCTION  Half2(n:number):number;
BEGIN
If (n = zero) Then zero;
If [ (n != zero) And (pred(n) = zero) ] Then zero;
If [ (n != zero) And (pred(n) != zero) ] Then succ(Half2(pred(pred(n))));
END.


FUNCTION Log2(n:number):number;
BEGIN
If (n = zero) Then zero;

If [ (n != zero) And (pred(n) = zero) ] Then zero; % One random comment.

If [ (n != zero) And (pred(n) != zero) ] Then succ(Log2(succ(Half2(pred(pred(n))))));
END.


%***************************************************************************
%************************* Function Bubble, pg. 147 ************************

FUNCTION  Bubble(x:list):list;
BEGIN
If (x = empty) Then x;

If [ (x != empty) And (tail(x) = empty) ] Then x;

If [ (x != empty) And (tail(x) != empty) And (Leq(head(x),head(tail(x))) = True) ]
                  Then add(head(tail(x)),Bubble(add(head(x),tail(tail(x)))));

If [ (x != empty) And (tail(x) != empty) And (Leq(head(x),head(tail(x))) = False) ]
                  Then add(head(x),Bubble(tail(x)));

END.

%***************************************************************************
%************************ Function ButLast, pg. 148 ************************

FUNCTION ButLast(x:list):list;
BEGIN
If (x = empty) Then empty;

If [ (x != empty) And (tail(x) = empty) ] Then empty;

If [ (x != empty) And (tail(x) != empty) ] Then add(head(x),ButLast(tail(x)));
END.

%***************************************************************************
%****************** Function Last, Walther ommits this  ********************

FUNCTION Last(x:list):number;
BEGIN
If (x = empty) Then zero;

If ( (x != empty) And (tail(x) = empty) ) Then head(x);

If ( (x != empty) And (tail(x) != empty) ) Then Last(tail(x));
END.



%***************************************************************************
%********************** Function BubbleSort, pg.148  ***********************

%FUNCTION BubbleSort(x:list):list;
%BEGIN
%If (x = empty) Then empty;
%
%If (x != empty) Then add(Last(Bubble(x)),BubbleSort(ButLast(Bubble(x))));
%END.

%***************************************************************************
%********************** Function Replace, pg.148  ***********************

FUNCTION Replace(n,m:number,x:list):list;
BEGIN
If (x = empty) Then empty;

If ( (x != empty) And (Equal(n,head(x)) = True) ) Then add(m,tail(x));

If ( (x != empty) And (Equal(n,head(x)) = False) ) Then add(head(x),Replace(n,m,tail(x)));

END.

%***************************************************************************
%******************** Function SelectSort, pg.148  *************************

FUNCTION SelectSort(x:list):list;
BEGIN

If (x = empty) Then empty;

If ( (x != empty) And (Equal(head(x),Minimum(x)) = True) ) Then 
                       add(head(x),SelectSort(tail(x)));

If ( (x != empty) And (Equal(head(x),Minimum(x)) = False) ) Then 
                       add(Minimum(x),SelectSort(Replace(Minimum(x),head(x),tail(x))));

END.


%***************************************************************************
%******************** Function DeleteMinimum, pg.149  **********************


FUNCTION DeleteMinimum(x:list):list;
BEGIN

If (x = empty) Then empty;

If ( (x != empty) And (tail(x) = empty) ) Then empty;

If ( (x != empty) And (tail(x) != empty) And (Leq(head(x),head(tail(x))) = True) ) 
                  Then add(head(tail(x)),DeleteMinimum(add(head(x),tail(tail(x)))));

If ( (x != empty) And (tail(x) != empty) And (Leq(head(x),head(tail(x))) = False) ) 
                  Then add(head(x),DeleteMinimum(tail(x)));

END.


%***************************************************************************
%*********************** Function MinSort, pg.149  *************************

FUNCTION MinSort(x:list):list;
BEGIN

If x = empty Then empty;

If x != empty Then add(Minimum(x),MinSort(DeleteMinimum(x)));

END.

%***************************************************************************
%******************** Function Smaller, pg.149  ***************************

FUNCTION  Smaller(n:number,x:list):list;
BEGIN
If (x = empty) Then empty;

If ( (x != empty) And (Less(n,head(x)) = True) ) Then Smaller(n,tail(x));

If ( (x != empty) And (Less(n,head(x)) = False) ) Then add(head(x),Smaller(n,tail(x)));

END.


%***************************************************************************
%********************** Function Larger, pg.150  ***************************

FUNCTION Larger(n:number,x:list) : list;
BEGIN

   If x = empty then empty;

   If ( (x != empty) And (Less(n,head(x)) = True) ) Then add(head(x),Larger(n,tail(x)));

   If ( (x != empty) And (Less(n,head(x)) = False) ) Then Larger(n,tail(x));

END.

%***************************************************************************
%********************** Function QuickSort, pg.150  ***************************

FUNCTION QuickSort(x:list):list;
BEGIN

  If x = empty Then empty;

  If x != empty Then Concat(QuickSort(Smaller(head(x),tail(x))),
                            add(head(x),QuickSort(Larger(head(x),tail(x)))));

END.

%***************************************************************************
%********************  Function DistributeOdd, pg.150  *********************

FUNCTION DistributeOdd(x:list):list;
BEGIN

If (x = empty) THEN empty;

If [ (x != empty) And (tail(x) = empty) ] Then x;

If [ (x != empty) And (tail(x) != empty) ] Then add(head(x),DistributeOdd(tail(x)));

END.


%***************************************************************************
%*******************  Function DistributeEven, pg.151  *********************


FUNCTION DistributeEven(x:list):list;
BEGIN

If (x = empty) THEN empty;

If [ (x != empty) And (tail(x) = empty) ] Then empty;

If [ (x != empty) And (tail(x) != empty) ] Then add(head(tail(x)),
                                                    DistributeEven(tail(tail(x))));

END.


%***************************************************************************
%******************** Function MergeSort, pg.151  **************************


FUNCTION MergeSort(x:list):list;
BEGIN

If x = empty THEN empty;

If ( (x != empty) And (tail(x) = empty) ) Then x;

If ( (x != empty) And (tail(x) != empty) ) Then Merge(MergeSort(DistributeOdd(x),
                                                      MergeSort(DistributeEven(x))));

END.













