Оборачивание рекурсивной функции для подсчета количества вызовов функции

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

Как отмечает Виктор, вы не можете взять рекурсивную функцию и «внедрить» некоторое поведение в место, где происходит рекурсивный вызов (потому что функция уже завершена).Вы должны будете предоставить некоторую точку расширения для этого.В решении Виктора это делается путем использования функции, которая будет вызываться рекурсивно, в качестве аргумента, что является наиболее общим решением.

Более простой вариант - использовать F # значение рекурсии , которое позволяет вамсоздать значение функции и использовать его в своем объявлении.Вы можете использовать это для создания рекурсивной функции, вызывая другую функцию, которая добавляет некоторое поведение к функции (например, подсчет):

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

factorial 10

Внутри лямбда-функции мы можем напрямую получить доступ к определяемой нами функции,поэтому нет необходимости, чтобы передаваемая функция вызывалась рекурсивно в качестве дополнительного параметра.Функция counted просто оборачивает данную функцию f и добавляет некоторые функциональные возможности:

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

Благодаря рекурсии значения функциональность будет добавлена ​​к функции factorial(и поэтому, когда он вызывает себя, он вызывает версию с добавленной поддержкой подсчета).