Urban Hafner

CTM: Exercise 3-8

Posted by Urban Hafner Thu, 15 Sep 2005 18:55:23 GMT

The problem

An iterative append. This exercise explores the expressive power of dataflow variables. In the declarative model, the following definition if append is iterative:

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

We can see this by looking at the expansion:

proc {Append Xs Ys ?Zs}
   case Xs
   of nil then Zs=Ys
   [] X|Xr then Zr in
      Zs=X|Zr
      {Append Xr Ys Zr}
   end
end

This can do a last call optimization because the unbound variable Zr ca be put in the list Zs and bound later. Now let us restrict the computation model to calculate with values only. How can we write an iterative append? One approach is to define two functions: (1) an iterative list reversal and (2) an iterative function that appends the reverse of a list to another list. Write an iterative append using this approach.

My solution

The iterative list reversal is already defined in the book in section 3.4.2.4. Taking this Append can be defined as follows:

local
   fun {IterAppend RevXs Ys}
      case RevXs
      of nil then Ys
      [] X|Xr then {IterAppend Xr X|Ys}
      end
   end
in
   fun {Append Xs Ys}
      {IterAppend {Reverse Xs} Ys}
   end
end