Agreed with your final conclusion, that it is generally faster. But stack space is limited compared to the amount of memory available, so there is a trade-off: use the stack for storage for speed, and limit yourself to the stack depth or use the storage memory with slower execution speed, but do not get caught by the stack space limit.
Thanks for rapp, Andras Pahi
-----Eredeti ?zenet----- Felad?: David Matthews [mailto:David.Matthews@prolingua.co.uk] K?ldve: Tuesday, October 16, 2007 10:17 PM C?mzett: Andr?s P?hi M?solatot kap: Lukas Bulwahn; PolyML mailing list T?rgy: Re: [polyml] Question about possible compiler optimization
Andr?s P?hi wrote:
What about this one?
fun mem l xs = let fun mem l (x :: xs) a = if x = l then (List.rev a) @ xs else mem l xs (x :: a) | mem l [] a = raise (Fail "Not found"); in mem' l xs [] end;
Almost, but append (@) is not tail-recursive so you need to combine List.rev and append. fun mem l xs = let fun rapp [] v = v | rapp (h::t) v = rapp t (h::v) fun mem' l (x :: xs) a = if x = l then rapp a xs else mem' l xs (x :: a) | mem' l [] a = raise (Fail "Not found"); in mem' l xs [] end;
The general point is that it's possible to avoid recursion by keeping the information elsewhere, in this case in the list. Generally, though, it's going to be faster to use the stack rather than build a list.
David