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.

Answer 3

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

This is almost it, but you have to understand more your problem, and maybe just the definition of f^n. you can define f^n by : for all x, f^n(x) = f^(n-1)(f(x)), and f^0(x) = x

In your code, you have f (n-1) g a, which is f^(n-1)(x) with my notations. You are never applying f, only at the end.

The solution is : f (n-1) g (g a) !!!

You have to apply g every time.

Answer 4

I happened to write a working version minutes ago:

let rec applyn n func arg =
if n <= 0 then
    arg
else
    applyn (n-1) func (func arg)

Notice the function application happens each time when the recursive call is made. In your code, g is called only once; OCaml can't infer it to be 'a -> 'a, so gives 'a -> 'b.