F# 中函数之间的循环依赖关系

Question

我正在尝试打破下面的循环依赖，但不确定最好的方法。

let cashOpeningBalance t =
if t = 1 then
    0.0
else
    cashClosingBalance (t - 1)
let cashInterest t = 
    cashOpeningBalance t * 0.03 
let accumulatedCash t =
    cashOpeningBalance t + cashInterest t
// let moreComplicatedLogic t = ...
let cashClosingBalance t =
    accumulatedCash t

使用这个答案中的一些逻辑，我想出了以下解决方案，但性能真的很差。

let cashOpeningBalance t cashClosingBalance =
if t = 1 then
    10.0
else
    cashClosingBalance (t - 1)
let cashInterest t cashClosingBalance = 
    (cashOpeningBalance t cashClosingBalance) * 0.03 
let accumulatedCash t cashClosingBalance =
    (cashOpeningBalance t cashClosingBalance) + (cashInterest t cashClosingBalance)
// let moreComplicatedLogic t cashClosingBalance = ...
let rec cashClosingBalance t =
    //accumulatedCash t cashClosingBalance
    let temp = accumulatedCash t cashClosingBalance
    printfn "Cash Closing Balance = %f Where t = %i" temp t
    temp
cashClosingBalance 3
(*
> 
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.609000 Where t = 2
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.300000 Where t = 1
Cash Closing Balance = 10.609000 Where t = 2
Cash Closing Balance = 10.927270 Where t = 3
val it : float = 10.92727
*)
cashClosingBalance 50
(*
Takes a really long time 
*)

有没有办法重写 cashClosesingBalance 函数来停止过多的递归调用，如下面的输出所示？我真的需要能够输入最多 400 的 t 值，并且它仍然可以在几秒钟内运行。

Answer 1

问题实际上不在于您在中间有moreComplicatedLogic（因此编写大let rec不方便）。问题是您的代码以低效的方式实现动态规划算法。

递归调用最终会使用相同的参数多次调用cashClosingBalance（而不是只调用一次并将结果存储在某个本地缓存中）。在函数式编程中，你可以使用一个相当通用的记忆概念来解决这个问题，但你可以以不同的方式重写你的算法，使其更有效率。

如果你想使用记忆，那么你需要这样的东西 - 下面的帮助程序获取一个函数并创建一个相同类型的函数来缓存以前调用的结果：

let memoize f = 
  let dict = System.Collections.Generic.Dictionary<_, _>() 
  fun v ->
    match dict.TryGetValue(v) with
    | true, res -> res
    | _ -> 
        let res = f v 
        dict.Add(v, res)
        res

然后你可以像这样使用memoize重写代码（我只是将所有函数定义包装在memoize中，并更改了参数的顺序，以便t是最后一个）：

let cashOpeningBalance cashClosingBalance = memoize (fun t ->
  if t = 1 then
    10.0
  else
    cashClosingBalance (t - 1))
let cashInterest cashClosingBalance = memoize (fun t -> 
    (cashOpeningBalance cashClosingBalance t) * 0.03 )
let accumulatedCash cashClosingBalance = memoize (fun t ->
    (cashOpeningBalance cashClosingBalance t) + (cashInterest cashClosingBalance t))
// let moreComplicatedLogic t cashClosingBalance = ...
let rec cashClosingBalance = memoize (fun t -> 
    //accumulatedCash t cashClosingBalance
    let temp = accumulatedCash cashClosingBalance t
    printfn "Cash Closing Balance = %f Where t = %i" temp t
    temp)