CODEWITHSUNDEEP
ocaml
Ghost
Ghost

Reputation: 407

N times function composition

I need to write a code that composes a function, f (x), with itself N times using recursive function.

What I wrote is:

let f x = x + 1 (*it can be any function*)
let rec compose n f x = if n = 0 then 
   "Can't compose anymore" 
else compose (n-1) f (f x);;

which is obviously not right. I know the code is not finished, but I do not know how to continue. Am I on the right path or not? Can you tell me how to solve the problem?

Upvotes: 2

Views: 844

Answers (1)

coredump
coredump

Reputation: 38809

You are on the right path. Based on the requirements, I would try to start from those equations:

compunere 1 f x == f x

The above says that applying f once to x is exactly the same as doing (f x).

compunere 2 f x == f (f x)

Likewise, applying f twice should compute f (f x). If you replace (f x) by a call to compunere, you have:

compunere 2 f x == f (f x) = f (compunere 1 f x)

The general pattern of recursion seems to be:

compunere n f x == f (compunere (n - 1) f x)

Note that the most general type of f is a -> b, but when f is called again with a value of type b, that means that a and b should be the same type, and so f really is an endomorphism, a function of type a -> a. That is the case for N >= 1, but in degenerate case of N=0, you could have a different behaviour.

Applying f zero time to x could mean "return x", which means that compunere could theoretically return a value of type a for zero, for any f being a a -> b function, a and b possibly distinct; you could distinguish both cases with more code, but here we can simply let the typechecker enforce the constraint that a = b in all cases and have an uniform behaviour. You can also make 0 invalid (like negative numbers) by throwing an exception (negative applications could theoretically be postitive applications of the inverse function, but you cannot compute that when knowing nothing about f; f could be non-invertible).

Your code is a little bit different:

compunere 3 f x == (compunere 2 f (f x))
                == (compunere 1 f (f (f x)))
                == (compunere 0 f (f (f (f x))))
...

The advantage of your approach is that the recursive call to compunere is directly giving the result for the current computation: it is in tail position which allows the compiler to perform tail-call elimination.

When you reach N=0, the value locally bound x gives the result you want. Here, for N=0 as an input, the only natural interpretation is also to return x.

Upvotes: 3

Related Questions