Wrapping a recursive function to count the number of function calls

Question

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

score 4 · Accepted Answer · answered Nov 13 '10 at 16:01

4

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.

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

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

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.

answered Nov 13 '10 at 16:01

Victor Nicollet

24,361
4
58
89

I'm stuck on 2 points, commenting out the dictionary, what types should go there now? And in wrap function the last line f recfun x I don't understand how this works :( – yanta Nov 13 '10 at 16:25
Dictionary: the same as before (the only difference is that now the type of f is `('a -> 'b) -> 'a -> 'b` because it expects `recfun`). `recfun` represents the function that should be called by `f` on the subdirectories (because `f` is not recursive anymore). This lets you use the counted function to work on the subdirectories – Victor Nicollet Nov 13 '10 at 16:30
let calls, counted_body = wrap body;; error FS0030: Value restriction. The value 'counted_body' has been inferred to have generic type val counted_body : ((string -> '_a) -> string -> seq) when '_a :> seq – yanta Nov 13 '10 at 16:38
Sounds like F# does not deduce that types `'b` are the same in `('a -> 'b) -> 'a -> 'b` (merely that the first may convert to the second). You will have to annotate `f` as `('a -> 'b) -> 'a -> 'b` and `recfun` as `'a -> 'b` manually. – Victor Nicollet Nov 13 '10 at 22:12
This technique is known as "untying the recursive knot". – J D Nov 15 '10 at 20:52

score 4 · Answer 2 · answered Nov 13 '10 at 16:15

As Victor points out, you cannot take a recursive function and "inject" some behavior into the place where the recursive call happens (because the function is already complete). You'll need to provide some extension point for that. In Victor's solution, this is done by taking a function to be called recursively as an argument, which is the most general solution.

A simpler option is to use F# value recursion which allows you to create a function value and use it in its declaration. You can use this to create a recursive function by calling another function that adds some behavior to the function (e.g. counting):

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

factorial 10

Inside the lambda function, we can directly access the function we're defining, so there is no need for passing function to be called recursively as additional parameter. The function counted simply wraps the given function f and adds some functionality:

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

Thanks to the value recursion, the functionality will be added to the factorial function (and so when it calls itself, it will call the version with added counting support).

This is simpler, and easier to understand, but Victors code is what I was trying to achieve. — yanta, Nov 13 '10 at 16:32

Wrapping a recursive function to count the number of function calls

2 Answers2

Linked