這個分割功能爲什麼起作用？

下面是函數：

let rec split = function 
    | []  -> ([],[]) 
    | [a]  -> ([a],[]) 
    | a::b::cs -> let (M,N) = split cs 
       (a::M, b::N)

我不明白的是爲什麼這種語句的工作(a::M, b::N)。我們不是在執行該語句之前調用遞歸函數嗎？那麼這種說法不應該被執行嗎？

來源

2017-03-05 name

嘗試寫下簡短列表的執行流程，您將看到它的工作原理。在某一時刻，你將開始匹配'[]'和'[a]'，這將導致遞歸一直展開到第一次調用。 – MarcinJuraszek

@MarcinJuraszek我做錯了，這就是爲什麼我感到困惑，但現在我明白了。謝謝！ – name

所發生的一切就是你的函數不是尾遞歸的。（在尾遞歸函數中，遞歸調用是函數中的最後一件事）。 F＃可以處理非尾遞歸函數。然而，由於你的函數不是尾遞歸，如果你提供一個長列表，堆棧將會炸燬。試試這個清單：'let xs = [1..1000000]'。爲了解決這個問題，你必須使用累加模式（或其他技術）重寫你的函數，以便它成爲尾遞歸。尾遞歸函數不會打擊堆棧。 – Soldalma

在我們執行該語句之前，我們不是調用遞歸函數嗎？

是的。

那麼該不該執行該聲明？

只有當遞歸是無限的時候，事實並非如此。原樣，(a::M, b::N)將在遞歸調用完成後進行評估。

作爲一個例子，考慮呼叫split [1;2;3]：

split [1;2;3] 
= let (M,N) = split [3] 
    (1::M, 2::N) 
= let (M,N) = ([3], []) 
    (1::M, 2::N) 
= (1::[3], 2::[]) 
= ([1;3], [2])

沒有無限怎麼回事。

來源

2017-03-05 21:50:24 sepp2k

我正在錯誤地做這個例子，這就是爲什麼我感到困惑。感謝您的幫助！ – name

這個分割功能爲什麼起作用？

回答

相關問題