包装一个递归函数以计算函数调用的数量 [英] Wrapping a recursive function to count the number of function calls

问题描述

说我有一个递归函数，我想知道每个输入值调用该函数的次数.除了放置printf表达式或更改返回类型以包括调用次数之外，是否可以将函数与另一个函数包装"以实现此目的?我希望包装函数返回函数调用的数量和原始函数的结果.它应该可以在不同的功能中重复使用.

Say I have a recursive function that I want to know how many times the function has called itself per input value. Rather than putting printf expressions or changing the return type to include the number of calls, is it possible to "wrap" the function with another to achive this? I would like the wrapped function to return the number of function calls and the original functions result. It should be reusable across different functions.

这是我所拥有的，它不起作用.

Here is what I have and it doesn't work.

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)]

推荐答案

这行不通，因为 getfilenames 被定义为调用 getfilenames ，而不是其他任何函数尤其是之后没有定义的功能.因此，只要您的包装器调用了该函数，该函数就会忽略您的包装器并开始调用自身.

This is not going to work, because getfilenames is defined as calling getfilenames, not any other function and especially not a function defined after that. So, as soon as your wrapper calls the function, the function will ignore your wrapper and start calling itself.

您需要做的是通过提供递归调用的函数作为参数，将递归从 getfilenames 函数移到另一个函数中.

What you need to do is move the recursion out of the getfilenames function and into another function, by providing the function to be called recursively as a parameter.

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 插入递归函数之前将其包装:

Now, you can wrap body before plugging it into a recursive function:

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 函数返回包装的函数(具有与原始函数相同的签名)和字典，以供外部访问.然后，可以在通话中找到通话次数.

Note that the wrap function returns both the wrapped function (with a signature identical to the original function) and the dictionary, for external access. The number of calls will then be found in calls.

这篇关于包装一个递归函数以计算函数调用的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！