Courses/CS 460/Fall 2005/Homework/Brian Smith/Oct 8

From CSWiki

[edit] MergeSort

% SMerge helper procedure
declare
proc {SMerge Xs Ys Zs}
   case Xs#Ys of nil#Ys then
      Zs = Ys
   [] Xs#nil then
      Zs = Xs
   [] (X|Xr) # (Y|Yr) then 
      if X =< Y then Zr in 
	 Zs = X|Zr
	 {SMerge Xr Ys Zr}
      else Zr in 
	 Zs = Y|Zr
	 {SMerge Xs Yr Zr}
      end 
   end 
end

%%% Top-down Merge Sort

declare A B C D
proc {MergeSort Li ?Lo}
   local Len Mid L1 L2 in
      Len = {Length Li}
      if Len =< 1 then
	 Lo = Li
      else
	 Mid = Len div 2
	 {List.takeDrop Li Mid L1 L2}
	 Lo = {SMerge {MergeSort L1} {MergeSort L2}}
      end
   end
end
% testing
A = {MergeSort [4 5 3 1 2]}
B = {MergeSort [y e m o s t h p z a i g x r]}
C = {MergeSort [1]}
D = {MergeSort nil}
{Browse [a#A b#B c#C d#D]}


%%% Bottom-up MergeSort

declare A B C D
proc {BUMergeSort Li ?Lo}
   local LL = {Split Li} in
      Lo = {RepeatMerge LL}
   end
end
fun {Split L}
   case L of H|T then
      [H] | {Split T}
   else
      nil
   end
end
proc {RepeatMerge LL ?Lo}
   case LL of [X] then
      Lo = X
   [] nil then
      Lo = nil
   else
      {Browse LL}
      Lo = {RepeatMerge {MergePairs LL}}
   end
end
proc {MergePairs LL ?Lo}
   case LL of H|nil then
      Lo = [H]
   [] H1|(H2|T) then
      Lo = {SMerge H1 H2} | {MergePairs T}
   else
      Lo = nil
   end
end
%testing
{Browse {BUMergeSort [e f c b d a]}}
{Browse {BUMergeSort [g e f c b d a]}}
{Browse {BUMergeSort [one]}}
{Browse {BUMergeSort nil}}

[edit] Other List Functions, Some Taking Procedures

%%% LAST %%%

declare A B C D
proc {Last Li ?X}
   case Li of H|nil then
      X = H
   [] _ | T then
      X = {Last T}
   else
      X = Li
   end
end
% testing
A = {Last [1 2 3 4 5]}
B = {Last [chocolate]}
C = {Last nil}
{Browse [last a#A b#B c#C]}


%%% NTH %%% (presented)

declare A B C D E
proc {Nth Li I ?X}
   case Li of H|T then
      if I == 1 then
	 X = H
      else
	 X = {Nth T (I-1)}
      end
   else
      X = 'out of bounds'
   end
end
%testing
A = {Nth [ape bear cat dog] 1}
B = {Nth [1 2 3 4] 3}
C = {Nth [1 2 3 4 5 6 7 8] 8}
D = {Nth [a b c] 4}
E = {Nth [d e f] 0}
{Browse [nth a#A b#B c#C d#D e#E]}


%%% APPEND %%%
% this version can append single elements
% and lists to the end of a list

declare A B C D
proc {Append Li X ?Lo}
   case X of H|nil then
      Lo = {Append Li H}
   [] H|T then
      Lo = {Append {Append Li H} T}
   else
      case Li of H|T then
	 Lo = H | {Append T X}
      else
	 Lo = [X]
      end
   end
end
% testing
A = {Append [1 2 3 4] 5}
B = {Append [a b c] [d e f]}
C = {Append nil [4.0 3.2 7.6]}
{Browse [append a#A b#B c#C]}


%%% REVERSE %%%

declare A B C D
proc {Reverse Li ?Lo}
   case Li of H|T then
      Lo = {Append {Reverse T} H}
   else
      Lo = nil
   end
end
% testing
A = {Reverse [dog cat bowl food]}
B = {Reverse [1]}
C = {Reverse nil}
{Browse [reverse a#A b#B c#C]}


%%% MAP %%%

declare A B C D
proc {Map Li P ?Lo}
   case Li of H|T then
      Lo = {P H} | {Map T P}
   else
      Lo = nil
   end
end
% testing
A = {Map [1 2 3 4] IntToFloat}
B = {Map [alligator bear 3 4.957 &t 'erc'] IsAtom}
C = {Map [8] IsOdd}
D = {Map nil IsFloat}
{Browse [map a#A b#B c#C d#D]}


%%% ZIP %%% (presented)

declare A B C D
proc {Zip L1 L2 P ?Lo}
   if {Length L1} == {Length L2} then
      case L1#L2 of (H1|T1)#(H2|T2) then
	 Lo = {P H1 H2} | {Zip T1 T2 P}
      else
	 Lo = nil
      end
   else
      Lo = 'Unequal length'
   end
end
% testing
A = {Zip [1 6 3] [4 5 6] Max}
B = {Zip [alligator zebra monkey frog] [tiger wallaby mongoose snake] Min}
C = {Zip [b r] [o k e n] Max}
{Browse [zip a#A b#B c#C]}