% Accumulators

% Merge-sort example

declare
fun {Merge Xs Ys}
   case Xs # Ys
   of nil # Ys then Ys
   [] Xs # nil then Xs
   [] (X|Xr) # (Y|Yr) then
      if X =< Y then X|{Merge Xr Ys}
      else Y|{Merge Xs Yr} end
   end
end

declare
fun {MergeSort Xs}
   fun {MergeSortAcc L1 N}
      if N == 0 then
	 nil # L1
      elseif N == 1 then
	 [L1.1] # L1.2
      elseif N > 1 then
	 NL = N div 2
	 NR = N - NL
	 Ys # L2 = {MergeSortAcc L1 NL}
	 Zs # L3 = {MergeSortAcc L2 NR}
      in
	 {Merge Ys Zs} # L3
      end
   end
in
   {MergeSortAcc Xs {Length Xs}}.1
end

{Browse {MergeSort [3 1 8 7 2 9]}}

% procedural version

declare
proc {MergeSort1 N S0 S Xs}
   if N==0 then S = S0 Xs = nil
   elseif N ==1 then X in X|S = S0 Xs = [X]
   else %% N > 1
      local S1 Xs1 Xs2 NL NR in
	 NL = N div 2
	 NR = N - NL
	 {MergeSort1 NL S0 S1 Xs1}
	 {MergeSort1 NR S1 S Xs2}
	 Xs = {Merge Xs1 Xs2}
      end
   end
end

declare
fun {MergeSort Xs}
   Ys in
   {MergeSort1 {Length Xs} Xs _ Ys}
   Ys
end


% Machine instructions example

declare SeqCode ExprCode

proc {SeqCode Es C0 C N0 N}
   case Es
   of nil then C = C0 N = N0
   [] E|Er then N1 C1 in
      {ExprCode E C0 C1 N0 N1}
      {SeqCode Er C1 C N1 N}
   end
end

proc {ExprCode Expr C0 C N0 N}
   case Expr
   of plus(Expr1 Expr2) then C1 N1 in
      C1 = plus|C0
      N1 = N0 + 1
      {SeqCode [Expr2 Expr1] C1 C N1 N}
   [] minus(Expr1 Expr2) then C1 N1 in
      C1 = minus|C0
      N1 = N0 + 1
      {SeqCode [Expr2 Expr1] C1 C N1 N}
   [] I andthen {IsInt I} then
      C = push(I)|C0
      N = N0 + 1
   end
end

local Code Size in
   {ExprCode plus(plus(2 3) minus(5 4)) nil Code 0 Size}
   {Browse Size#Code}
end

% shorter version

declare 
proc {ExprCode Expr C0 C N0 N}
   case Expr
   of plus(Expr1 Expr2) then
      {SeqCode [Expr2 Expr1] plus|C0 C N0 + 1 N}
   [] minus(Expr1 Expr2) then
 	{SeqCode [Expr2 Expr1] minus|C0 C N0 + 1 N}
   [] I andthen {IsInt I} then
      C = push(I)|C0
      N = N0 + 1
   end
end

% using functions rather than procedures

declare ExprCode SeqCode

fun {ExprCode Expr t(C0 N0) }
   case Expr
   of plus(Expr1 Expr2) then
      {SeqCode [Expr2 Expr1] t(plus|C0 N0 + 1)}
   [] minus(Expr1 Expr2) then
      {SeqCode [Expr2 Expr1] t(minus|C0 N0 + 1)}
   [] I andthen {IsInt I} then
      t(push(I)|C0 N0 + 1)
   end
end

fun {SeqCode Es T}
   case Es
   of nil then T
   [] E|Er then 
      T1 = {ExprCode E T} in
      {SeqCode Er T1}
   end
end

{Browse {ExprCode plus(plus(2 3) minus(5 4)) t(nil 0)}}

% Difference lists

declare
fun {AppendD D1 D2}
   S1 # E1 = D1
   S2 # E2 = D2
in
   E1 = S2
   S1 # E2
end

local X Y in {Browse {AppendD (1|2|3|X)#X (4|5|Y)#Y}} end

% a queue with difference lists

declare NewQueue Insert Delete EmptyQueue

fun {NewQueue} X in q(0 X X) end

fun {Insert Q X}
	case Q of q(N S E) then E1 in E=X|E1 q(N+1 S E1) end 
end

fun {Delete Q X}
	case Q of q(N S E) then S1 in X|S1=S q(N-1 S1 E) end
end

fun {EmptyQueue Q} case Q of q(N S E) then N==0 end end

declare Q1 Q2 Q3 Q4

Q1 = {NewQueue}
{Browse Q1}

Q2 = {Insert Q1 a}
{Browse Q2}

Q3 = {Insert Q2 b}
{Browse Q3}

local X in Q4 = {Delete Q3 X} {Browse X} end
{Browse Q4}

% A problem with difference lists:
declare Q5
Q5 = {Insert Q2 c}
{Browse Q5}

   
% Flattening nested lists

declare
fun {IsLeaf N}
   {Not {IsList N}}
end

declare
fun {Flatten Xs}
case Xs
   of nil then nil
   [] X|Xr andthen {IsLeaf X} then
     X|{Flatten Xr}
   [] X|Xr  andthen {Not {IsLeaf X}} then
      {Append {Flatten X} {Flatten Xr}}
   end
end

{Browse {Flatten [[1] 2 [[3] 4]]}}

% flattening with difference lists

declare
proc {FlattenD Xs Ds}
   case Xs
   of nil then Y in Ds = Y#Y
   [] X|Xr  then Y0 Y1 Y2 in
      Ds = Y0#Y2
      {FlattenD X Y0#Y1}
      {FlattenD Xr Y1#Y2}
   [] X andthen {IsLeaf X} then Y in Ds = (X|Y)#Y
   end
end

declare
fun {Flatten Xs}  Y in {FlattenD Xs Y#nil}  Y end

% reversing a list

declare
fun {Reverse Xs}
	case Xs
	of nil then nil
	[] X|Xr then {Append {Reverse Xr} [X]}
	end
end

{Browse {Reverse [1 2 3 4]}}

% using difference lists

declare
fun {ReverseD Xs}
   proc {ReverseD Xs Y1 Y}
      case Xs
      of nil then Y1=Y
      [] X|Xr then Y2 in
	 {ReverseD Xr Y1 Y2}
	 Y2 = X|Y
      end
   end
   R in
   {ReverseD Xs R nil}
   R
end

{Browse {ReverseD [1 2 3 4]}}

% making it iterative

declare
fun {ReverseD Xs}
   proc {ReverseD Xs Y1 Y}
      case Xs
      of nil then Y1=Y
      [] X|Xr then
	 {ReverseD Xr Y1 X|Y}
      end
   end
   R in
   {ReverseD Xs R nil}
   R
end