包装一个递归函数来计算函数调用的数量

Question

说我有一个递归函数，我想知道函数每次输入值调用它自己的次数。而不是把printf表达式或改变返回类型以包含调用次数，是否有可能用另一个“包装”这个函数来实现这个功能？我希望包装函数返回函数调用的数量和原始函数的结果。它应该可以跨不同的功能重用。

这是我有，它不工作。

open System 
open System.IO 
open System.Collections.Generic 

/// example recursive function 
let rec getfilenames dir = 
    seq { 
     yield Directory.GetFiles dir 
     for x in Directory.GetDirectories dir do yield! getfilenames x} 

/// function to count the number of calls a recursive function makes to itself 
let wrapped (f: 'a -> 'b) = 
    let d = new Dictionary<'a, int>() 

    fun x -> 
     let ok, res = d.TryGetValue(x) 
     if ok then d.[x] <- d.[x] + 1 
     else 
      d.Add(x, 1) 
     d, f x 

> let f = wrapped getfilenames 
let calls, res = f "c:\\temp";; 

val f : (string -> Dictionary<string,int> * seq<string []>) 
val res : seq<string []> 
val calls : Dictionary<string,int> = dict [("c:\temp", 1)] 

Answer 1

这是行不通的，因为getfilenames被定义为调用getfilenames，没有任何其他功能，特别是不要之后定义的函数。所以，只要你的包装调用函数，该函数将忽略你的包装，并开始调用自己。

您需要做的是将递归移出getfilenames函数，并将函数递归地作为参数提供给另一个函数。现在

let body recfun dir = 
    seq { 
     yield Directory.GetFiles dir 
     for x in Directory.GetDirectories dir do yield! recfun x} 

let rec getfilenames dir = body getfilenames dir 

，你可以将其插入一个递归函数之前包裹body：

let wrap f = 
    let d = (* ... *) in 
    d, fun recfun x -> 
     let ok, res = d.TryGetValue(x) 
     if ok then d.[x] <- d.[x] + 1 
     else d.Add(x, 1) 
     f recfun x 

let calls, counted_body = wrap body 

let getfilenames dir = counted_body getfilenames dir 

注意，wrap函数返回两个包裹函数（等同于原有功能的签名）和字典，用于外部访问。然后在calls找到电话的数量。

Answer 2

正如Victor指出的那样，您不能采用递归函数并将某些行为“注入”发生递归调用的位置（因为函数已经完成）。您需要为此提供一些扩展点。在Victor的解决方案中，这是通过将函数作为参数递归调用来完成的，这是最一般的解决方案。

一个更简单的选项是使用F＃值递归它允许您创建一个函数值并在其声明中使用它。您可以使用此调用另一个函数，增加了一些行为的函数来创建一个递归函数（如计数）：

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

factorial 10 

里面的lambda函数，我们可以直接访问我们定义的函数，所以有无需传递函数作为附加参数递归调用。功能counted只是封装给定的函数f，并增加了一些功能：

let counted f = 
    let count = ref 0 
    (fun x -> 
    count := !count + 1; 
    printfn "call: %d" (!count) 
    f x) 

得益于值递归，该功能将被添加到factorial功能（所以当它调用本身，它会调用版本增加计数支持）。