尾递归和布尔运算符

我目前正在学习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

尾递归和布尔运算符

回答

相关问题