Oliver Mooney wrote:
Hi all,
I'm working my way through the exercises in CTM by myself, so
apologies if you see a lot of questions about them!
Exercise 3.16 seeks a tail-recursive function for convoluting lists,
and asks that the solution convolutes two lists in the same number of
recursive calls as there are elements in the list. Convoluting the two
lists [a b c] and [1 2 3] should result in three recursive calls
ultimately constructing the list [a#3 b#2 c#1].
The question gives a hint about how the function can calculate the
reverse of the second list and use that as an input to recursive calls
to itself, since the order of unification doesn't matter.
I devised the following solution but it doesn't seem to be addressing
the meat of the issue (though it works), since the order of
unification is the standard in-order one:
declare Convolute
fun {Convolute L1 L2}
fun {ConvoluteAcc L1 L2}
case L1 of
H1|T1 then
case L2 of
H2|T2 then
H1#H2|{ConvoluteAcc T1 T2}
end
[] nil then nil
end
end
in
{ConvoluteAcc L1 {Reverse L2}}
end
This is not right because you are doing 2n recursive calls (n in Reverse
and n in ConvoluteAcc).
You are allowed only 1 function that makes n recursive calls!
What is the exercise trying to get me to see? That I should somehow
incrementally calculate the reverse of the second list in each
recursive call? I've rolled my own Reverse function for lists below
but I'm not seeing how to adapt that structure to the above problem...
You have to combine ConvoluteAcc and Reverse into a single function that
calculates both.
It calculates the reversed list and also takes the reversed list as
input. This works because
unification is order-independent.
Peter
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
