2015-04-01 110 views
0

我不明白尾遞歸和List.fold_left之間的區別?尾遞歸與List.fold_left

有什麼區別?我應該在什麼時候使用尾遞歸和List.fold_left

+1

尾遞歸是一種編程概念,而'List.fold_left'是一個使用它的函數?你的問題還不太清楚...... – PatJ 2015-04-01 22:31:19

+0

新來者的典型混亂之一...... – camlspotter 2015-04-02 01:11:17

回答

1

List.fold_left是迭代序列的泛函。它是一個函數,它接受一個列表,一些初始值,並將這個函數按順序應用到列表中的每個元素。這是函數式編程中衆所周知的higher order函數。它通常用於循環和迭代,而不是直接使用遞歸。

當函數本身調用時,尾遞歸是尾調用的一種特殊情況。基本上,一個調用是尾部的,如果它是函數中的最後一個表達式。所以在通話之後,不需要再進行任何評估。尾調用在OCaml中進行了簡化的迭代,即它們不像正常的調用那樣消耗棧。

List.fold_left是使用遞歸實現的,並且標準實現中的所有遞歸調用都位於尾部位置。還有一些是List.fold_right,有些時候是以非遞歸方式實現的。

3

如果你的問題是「我能做什麼用,我不能使用fold_left,反之亦然尾遞歸」,得到的回答是:

凡是可以使用fold_left實現可以使用尾遞歸的實現fold_left本身通常使用尾遞歸來實現。以下幾點可以使用尾遞歸來實現,但不是fold_left

  • 任何事情如果你遍歷比列表以外的東西(比如你正在迭代直到整數爲0)。
  • 任何你迭代一個列表而不是一次一個元素的地方。
  • 任何你迭代列表的地方,但你可能會停止,直到結束。