Рекурсия хвоста и булевы операторы

В настоящее время я изучаю 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: // StackOverflow. com/questions/15031382/can-a-function-be-optimized-for-tail-recursion-even-when-there-are-more-than-one) – joce

@Joce Хотя этот вопрос имеет некоторое сходство с вашим, он отличается чтобы гарантировать его открытость. –

Я собрал вторую версию вашего «существует» функции и «hasNoRoot» с VS2012 (F # 3.0) и оптимизациями, затем проверил IL, произведенный компилятор с использованием .NET Reflector. Компилятор делает оптимизацией функции «hasNoRoot», но, к сожалению, не оптимизирует функцию «существует». Похоже, что это разумная оптимизация, поэтому, возможно, она будет добавлена к следующей версии компилятора.

Для потомков, вот что компилятор:

.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

Спасибо за ваш ответ. Это отвечает на мой вопрос. –

Рекурсия хвоста и булевы операторы

ответ

Смежные вопросы