Function composition

Question
1

def iter[A](f: A => A, n: Int): A => A

I am just beginner of scala… and I have no idea way of understanding above method… Please help me.

  1. What is ‘A’? I guess it is a type… but what is that exactly.

  2. How to make a method that makes composition of function f with respect to number of ‘n’?

Thank you

2

A is a type parameter, it means it can be anything, and will infer the correct type when the function is defined.

So for example if you do this:

val plus1: Int => Int = x => x + 1

val plus5: Int => Int = iter(plus1, 5)

Then A will be inferred as Int, you may remove that and rather use Int or any other type, the solution will be the same.
About how to implement it, I would use a simple (tail) recursion.

3

Thank you for your reply

so iter is a function that takes function(f) and n(int) and returns a function?

and A is just a type

4

and I wrote the code for the solution, and I don’t know how to pass just type A for f function

def iter[A](f: A => A, n: Int): A => A = {

if (n == 1) {

f

} else {

f(iter(f,n-1))

}
}

val f: Int => Int = x => x + 1

println(iter(f,1))

5

Note that the question was answered in SO.
Anyways, let me try to answers some of the remaining questions.

so iter is a function that takes function(f) and n(int) and returns a function?

Yes.

and A is just a type

Correct again.

and I don’t know how to pass just type A for f function

You don’t need to pass the A type to the f function, more over you can’t pass the A type to the f function, since the f function doesn’t receive any A type.
Maybe you want to know how to pass a value of type A to the f function, but you don’t need to do that, since you don’t need to call the function you just need to compose it with itself multiple times to produce a new function.

iter(f, n-1)(f(x))?? is this just the library function that scala has?

Not sure what you mean with “library function that scala has” but, with this code:

def iter[A](f: A => A, n: Int): A => A =
  if (n == 0) identity else x => iter(f, n-1)(f(x))

What we are doing is very simple, let’s run the code by hand:

val plus1: Int => Int = x => x + 1
iter(plus1, 2)

if (2 == 0) identity else x => iter(plus1, 2-1)(plus1(x)) // By definition of iter
x => iter(plus1, 1)(plus1(x))  // By evaluation of the if and the -

Quick break, note that here we are creating a new function, the type of this function is inferred to be A => A since this is the last expression of the iter method, thus this is the return expression of the ìter method. So, the x there is a value of type A, iter(plus1, 1) returns another function of type A => A and finally plus1(x) returns a value of type A and then we are passing that value to the function returned to iter(plus1, 1) which would return another A
Note: f(x) is the same as f.apply(x) which is just basically calling the function.
Let’s continue with the evaluation:

x => iter(plus1, 1).apply(plus1(x))

x => (if (1 == 0) identity else x' => iter(plus1, 1-1).apply(plus1(x'))).apply(plus1(x))  // By definition of iter
x => (x' => iter(plus1, 0).apply(plus1(x'))).apply(plus1(x)) // By evaluation of the if and the -
x => (x' => (if (0 == 0) identity else x'' => iter(plus1, 0-1).apply(plus1(x''))).apply(plus1(x'))).apply(plus1(x)) // By definition of iter
x => (x' => (identity).apply(plus1(x'))).apply(plus1(x)) // By evaluation of the if
x => (x' => (y => y).apply((y => y + 1).apply(x'))).apply((y => y + 1).apply(x)) // By definition of plus1 & identity
x => (x' => (y => y).apply(x' + 1)).apply(x + 1) // By evaluation of plus1
x => ((y => y).apply((x + 1) + 1)) // By evaluation of the inner x' function.
x => (x + 1) + 1 // By evaluation of the inner y function.
x => x + 2 // By evaluation of +

So as you can see iter(plus1, 2) ends up creating a function that is equivalent to x + 2
Hope that helps.

1 Like