計算陣列的長度而不會炸掉堆棧

如何在不炸掉堆棧的情況下計算陣列的長度？我的兩次嘗試不看對我好計算陣列的長度而不會炸掉堆棧

let rec slowComputeLength xs = match xs with 
           | x::xss -> 1 + slowComputeLength xss 
           | _ -> 0 

let computeLength xs = List.fold (fun acc _ -> acc + 1) 0 xs

我能想到通過蓄能器在模式匹配的第一個版本，但是，使API醜陋

let rec slowComputeLength xs acc = match xs with 
            | x::xss -> slowComputeLength xss acc+1 
            | _ -> 0

是List.fold的正確方法還是創造了一些類似於下面的東西，我相信它也是一樣？

(1 + (1 + (1 + (...))))?

PS - 我在做這個練習，理想情況下我們應該使用Array.Length。

來源

2016-07-07 Rohit Sharma

啊是的，這是一個練習。我想補充一點。 :) –

哇，表達式'slowComputeLength xss acc + 1'是* evil *。與'_ - > 0'一起，它實際上導致了正確的結果，但完全沒有做它看起來應該做的事情。這不是尾遞歸：請注意，函數應用比'+'運算符具有更高的優先級！ – Vandroiy

'List.fold'循環，可能是通過尾遞歸在發佈的答案，所以它不會吹堆棧。 – phoog

通常招是定義保持累加器嵌套遞歸函數：

let computeLength xs = 
    let rec loop acc xs = 
    match xs with 
    | _::xs -> loop (acc+1) xs 
    | _ -> acc 
    loop 0 xs

這裏，loop函數具有附加蓄能器的參數，但它不會使外computeLength函數的API難看，因爲loop函數是嵌套的，並且從不直接由用戶調用。

來源

2016-07-07 14:45:53

您是否想到答案，它出現了？那不到一分鐘。 –

我只是隨意瀏覽SO，問題出現:)。公平起見，我沒有測試代碼... –

謝謝，也是我的假設正確的List.Fold會創建堆棧幀，因爲它迭代？如果迭代結束時列表被摺疊（抱歉，如果這不是正確的術語），還是隨着它的增加而積累？ –

計算陣列的長度而不會炸掉堆棧

回答

相關問題