How much space is required in my SML code?

Question

I have SML code like below.

fun fact(n) =
    let fun f(n,g) = if n=0 then g(1)
                     else f(n-1, fn x=>g(x)*n)
in f(n, fn x=> x) end;

I want to know how much space is required in my code for computing fact(n). Is it right it requires O(n)? I don't know exactly.

Answer 1

Yes, the function you wrote creates n closures before evaluating them at the end.

Here is a more space-efficient version:

fun fact n =
    let fun fact' 0 result = result
          | fact' n result = fact' (n-1) (n*result)
    in fact' n 1 end

It resolves n*result before making a recursive call, rather than delaying it, making it tail-recursive.