包裝一個遞歸函數來計算函數調用的數量

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功能（所以當它調用本身，它會調用版本增加計數支持）。