OCaml recursive function to apply a function n times

Question

I want to create a function of type int -> ('a -> 'a) -> 'a -> 'a in OCaml that takes an int n (non-neg) and a function f 'a -> 'a and an argument a of type 'a. f should be called on a n times.

I've tried 3 different things but can only get int -> ('a -> 'b) -> 'a -> 'b, here are a few things I've tried.

let rec f n g a = 
g a;
f (n-1) g a;;

which gives

val f : int -> ('a -> 'b) -> 'a -> 'c = <fun>

and I've tried

    let rec f n g a =
  if n > 0 then f (n-1) g a
  else g a
  ;;

which gave me

val f : int -> ('a -> 'b) -> 'a -> 'b = <fun>

The second is closer but I'm at a loss for how to get int -> ('a -> 'a) -> 'a -> 'a

Answer 1

I'm not quite sure about what you are trying to do. I guess it is the function below:

let rec foldi i f acc =
    if i <= 0 then acc else foldi (pred i) f (f acc)

which recursively apply i times the function f to a value acc and then to its its result. foldi might not be the best name for it though.

Answer 2

The type will straighten out once you get the function written correctly. The problem with your second attempt is that it gives the wrong answer for f5 0 .... It seems to me you don't want to apply the function at all in that case.

Maybe the following example will show what I mean:

# let add1 x = x + 1;;
val add1 : int -> int = <fun>
# f5 2 add1 3;;
- : int = 5
# f5 1 add1 3;;
- : int = 4
# f5 0 add1 3;;
- : int = 3
# 

These are the answers you should get, it seems to me.