结合记忆化和尾递归

问题描述

是否有可能以某种方式将记忆化和尾递归结合起来?我目前正在学习 F# 并理解这两个概念，但似乎无法将它们结合起来.

Is it possible to combine memoization and tail-recursion somehow? I'm learning F# at the moment and understand both concepts but can't seem to combine them.

假设我有以下 memoize 函数(来自 Real-World Functional Programming):

Suppose I have the following memoize function (from Real-World Functional Programming):

let memoize f = let cache = new Dictionary<_, _>()
                (fun x -> match cache.TryGetValue(x) with
                          | true, y -> y
                          | _       -> let v = f(x)
                                       cache.Add(x, v)
                                       v)

和下面的factorial函数:

let rec factorial(x) = if (x = 0) then 1 else x * factorial(x - 1)

记忆 factorial 并不太难，而且使它成为尾递归也不是:

Memoizing factorial isn't too difficult and making it tail-recursive isn't either:

let rec memoizedFactorial =
  memoize (fun x -> if (x = 0) then 1 else x * memoizedFactorial(x - 1))

let tailRecursiveFactorial(x) =
  let rec factorialUtil(x, res) = if (x = 0)
                                  then res
                                  else let newRes = x * res
                                       factorialUtil(x - 1, newRes)
  factorialUtil(x, 1)

但是你能把记忆化和尾递归结合起来吗?我做了一些尝试，但似乎无法让它工作.或者这根本不可能?

But can you combine memoization and tail-recursion? I made some attempts but can't seem to get it working. Or is this simply not possible?

推荐答案

与往常一样，延续会产生一个优雅的尾调用解决方案:

As always, continuations yield an elegant tailcall solution:

open System.Collections.Generic

let cache = Dictionary<_,_>()  // TODO move inside
let memoizedTRFactorial =
    let rec fac n k =  // must make tailcalls to k
        match cache.TryGetValue(n) with
        | true, r -> k r
        | _ ->
            if n=0 then
                k 1
            else
                fac (n-1) (fun r1 ->
                    printfn "multiplying by %d" n  //***
                    let r = r1 * n
                    cache.Add(n,r)
                    k r)
    fun n -> fac n id

printfn "---"
let r = memoizedTRFactorial 4
printfn "%d" r
for KeyValue(k,v) in cache do
    printfn "%d: %d" k v

printfn "---"
let r2 = memoizedTRFactorial 5
printfn "%d" r2

printfn "---"

// comment out *** line, then run this
//let r3 = memoizedTRFactorial 100000
//printfn "%d" r3

有两种测试.首先，这个演示调用 F(4) 缓存 F(4)、F(3)、F(2)、F(1).

There are two kinds of tests. First, this demos that calling F(4) caches F(4), F(3), F(2), F(1) as you would like.

然后，注释掉 *** printf 并取消注释最终测试(并在发布模式下编译)以表明它没有 StackOverflow(正确使用尾调用).

Then, comment out the *** printf and uncomment the final test (and compile in Release mode) to show that it does not StackOverflow (it uses tailcalls correctly).

也许我会概括出 'memoize' 并在接下来的 'fib' 上演示它...

Perhaps I'll generalize out 'memoize' and demonstrate it on 'fib' next...

编辑

好的，我认为这是下一步，将记忆与阶乘分离:

Ok, here's the next step, I think, decoupling memoization from factorial:

open System.Collections.Generic

let cache = Dictionary<_,_>()  // TODO move inside
let memoize fGuts n =
    let rec newFunc n k =  // must make tailcalls to k
        match cache.TryGetValue(n) with
        | true, r -> k r
        | _ ->
            fGuts n (fun r ->
                        cache.Add(n,r)
                        k r) newFunc
    newFunc n id
let TRFactorialGuts n k memoGuts =
    if n=0 then
        k 1
    else
        memoGuts (n-1) (fun r1 ->
            printfn "multiplying by %d" n  //***
            let r = r1 * n
            k r)

let memoizedTRFactorial = memoize TRFactorialGuts

printfn "---"
let r = memoizedTRFactorial 4
printfn "%d" r
for KeyValue(k,v) in cache do
    printfn "%d: %d" k v

printfn "---"
let r2 = memoizedTRFactorial 5
printfn "%d" r2

printfn "---"

// comment out *** line, then run this
//let r3 = memoizedTRFactorial 100000
//printfn "%d" r3

编辑

好的，这是一个似乎有效的完全通用的版本.

Ok, here's a fully generalized version that seems to work.

open System.Collections.Generic

let memoize fGuts =
    let cache = Dictionary<_,_>()
    let rec newFunc n k =  // must make tailcalls to k
        match cache.TryGetValue(n) with
        | true, r -> k r
        | _ ->
            fGuts n (fun r ->
                        cache.Add(n,r)
                        k r) newFunc
    cache, (fun n -> newFunc n id)
let TRFactorialGuts n k memoGuts =
    if n=0 then
        k 1
    else
        memoGuts (n-1) (fun r1 ->
            printfn "multiplying by %d" n  //***
            let r = r1 * n
            k r)

let facCache,memoizedTRFactorial = memoize TRFactorialGuts

printfn "---"
let r = memoizedTRFactorial 4
printfn "%d" r
for KeyValue(k,v) in facCache do
    printfn "%d: %d" k v

printfn "---"
let r2 = memoizedTRFactorial 5
printfn "%d" r2

printfn "---"

// comment out *** line, then run this
//let r3 = memoizedTRFactorial 100000
//printfn "%d" r3

let TRFibGuts n k memoGuts =
    if n=0 || n=1 then
        k 1
    else
        memoGuts (n-1) (fun r1 ->
            memoGuts (n-2) (fun r2 ->
                printfn "adding %d+%d" r1 r2 //%%%
                let r = r1+r2
                k r))
let fibCache, memoizedTRFib = memoize TRFibGuts
printfn "---"
let r5 = memoizedTRFib 4
printfn "%d" r5
for KeyValue(k,v) in fibCache do
    printfn "%d: %d" k v

printfn "---"
let r6 = memoizedTRFib 5
printfn "%d" r6

printfn "---"

// comment out %%% line, then run this
//let r7 = memoizedTRFib 100000
//printfn "%d" r7

这篇关于结合记忆化和尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！