% 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