我的SML代碼需要多少空間？

Question

我有像下面的SML代碼。

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; 

我想知道我的代碼中需要多少空間來計算fact（n）。 它是否需要O（n）？我不完全清楚。

Answer 1

是的，你寫的函數創建了n在最後評估它們之前關閉。

這裏是一個更節省空間的版本：

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

它使一個遞歸調用，而不是推遲它，使它尾遞歸解析之前n*result。