CTM: Exercise 3-7
Posted by Urban Hafner
The problem
Another append function. Section 3.4.2 defines the Append function by doing recursion on the first argument. What happens if we try to do recursion on the second argument? Here is a possible solution:
fun {Append Ls Ms}
case Ms
of nil then Ls
[] X|Mr then {Append {Append Ls [X]} Mr}
end
endIs this program correct? Does it terminate? Why or why not?
My solution
On first sight this definition seems to be correct. But of course it isn’t. This is an exercise from a CS textbook, so when a question like “Is this correct?” is asked is clear that the answer has to be “No!” :)
Anyway, here’s why this definition of Append is wrong: The problem is the inner call to Append. In this call Ms is bound to [X] which is the same as X|nil. But this means that it will always go into the second branch of the case statement. It will take apart the list and create the very same list for the inner call to Append again! So the inner Append actually never returns!
Apart from that the two lists can’t be appended together as nowhere in this Append function two lists are actually appended together using the | operator. So it’s doubly wrong.
