尾遞歸和布爾運算符

我目前正在學習F＃（通過try f＃網站）。我有以下（imho）一元謂詞存在量化的尾遞歸函數（int-> bool）。尾遞歸和布爾運算符

let rec exists bound predicate = 
    if (bound<0) then false 
    elif predicate(bound) then true 
    else exists (bound-1) predicate

現在，這個功能也可以寫成

let rec exists bound predicate = (bound+1>0) && (predicate(bound) || exists (bound-1) predicate)

然而，第二個實現不是尾遞歸。問題是編譯器是否將它優化爲尾遞歸？

如何是更簡單的情況（好吧，這是一個有點傻）的例子，說

let rec hasNoRoot f = 
    if (f x = 0) then false 
    else hasNoRoot (fun x -> f (x+1))

與

let rec hasNoRoot f = (f 0 <> 0) && (hasNoRoot (fun x-> f(x+1)))

在第二個例子

，爲了識別功能（它的描述實際上）作爲尾遞歸，編譯器只需要「知道」爲了評估一個連接點，不一定必須評估兩個連接詞。

感謝您的任何意見

來源

2013-04-06 D.F.F

的可能重複[？可一個功能，即使有多個不同的遞歸調用尾遞歸優化（HTTP：//計算器。 com/questions/15031382/can-a-function-be-optimized-for-tail-recursion-even-when-there-more-one） – joce 2013-04-06 21:54:06

@Joce雖然這個問題與你有一些相似之處，但它與衆不同足以保證保持開放。 – 2013-04-06 22:06:19

我編譯使用.net反射編譯器生成你的「存在」和「hasNoRoot」功能與VS2012（F＃3.0）和優化，然後檢查了IL的第二個版本。編譯器確實優化'hasNoRoot'函數，但不幸的是，並沒有優化'exists'函數。這似乎是一個合理的優化，所以它可能會被添加到編譯器的下一個版本中。

對於後人，這裏是編譯器生成的：

.method public static bool exists(int32 bound, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool> predicate) cil managed 
{ 
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { new int32[int32(0x2)] { int32(0x1), int32(0x1) } } 
    .maxstack 8 
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: ldc.i4.1 
    L_0003: add 
    L_0004: ldc.i4.0 
    L_0005: ble.s L_001c 
    L_0007: ldarg.1 
    L_0008: ldarg.0 
    L_0009: callvirt instance !1 [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool>::Invoke(!0) 
    L_000e: brfalse.s L_0012 
    L_0010: ldc.i4.1 
    L_0011: ret 
    L_0012: ldarg.0 
    L_0013: ldc.i4.1 
    L_0014: sub 
    L_0015: ldarg.1 
    L_0016: starg.s predicate 
    L_0018: starg.s bound 
    L_001a: br.s L_0001 
    L_001c: ldc.i4.0 
    L_001d: ret 
}

來源

2013-04-06 21:53:16

感謝您的回覆。這回答了我的問題。 – 2013-04-06 22:10:58

尾遞歸和布爾運算符

回答

相關問題