0
votes

I was looking at examples of currying technique in scala and didn't understand how a function can return another function when a function is recursive.

for example I understand this code

def addOne(x: Int): Int = x => x + 1
def repeater(myFunc: Int => Int, n: Int, x:Int): Int = 
    if(n<=0) x
    else repeater(myFunc, n-1, myFunc(x))

above one is ok for me, if I say repeater(addOne, 10, 1) returns 11. Till n equals to zero, I decrease n with 1, and recursion stack starts working bottom to up.

But this one confuses me

def repeater(myFunc: Int => Int, n:Int): Int => Int = {
   if(n<=0) (x:Int) => x
   else (x: Int) => repeater(myFunc, n-1)(myFunc(x))
}

The point that I don't understand here, for example, if I run repeater(addOne, 2) it will look the else part and else part says to return a function, so program returns a function at first, or execute repeater one more time with n-1 (1-1) and return another function? This else part return how many functions, and what will the call stack look like?

3

3 Answers

2
votes

Let's unfold the recursion step by step.

repeater(addOne, 2) returns new anonymous function

(x:Int) => repeater(addOne, 1).apply(addOne(x))

Where repeater(addOne, 1) returns new anonymous function

(x:Int) => repeater(addOne, 0).apply(addOne(x))

Where repeater(addOne, 0) returns new anonymous function

(x:Int) => x

Therefore repeater(addOne, 1) returns an anonymous function which looks like

(y:Int) => {
    ((x: Int) => {
        x
    }).apply(addOne(y))
}

And repeater(addOne, 2) returns an anonymous function which looks like

(z:Int) => {
    ((y: Int) => {
        ((x: Int) => {
            x
        }).apply(addOne(y))
    }).apply(addOne(z))
}
2
votes

First, let's clarify that if you ran repeater(addOne, 3), you would only get back a function. You would need to runrepeater(addOne, 3)(SomeOtherInteger) to get your integer value and the result of your computation. All that the recursion is doing here is constructing a function. repeater(addOne, 3) returns a function that takes in an integer and returns an integer. Take the example of repeater(addOne, 3), if we write out the result of the recursion fully, this is what we get

{ x => {x => { x => { x => x }(myFunc(x)) }(myFunc(x)) }(myFunc(x))) }

It might look a bit confusing but lets break it down.

Lets focus on the innermost part - { x => x }(myFunc(x)). This can be seperated into two parts, a function and an input to the function. The function is { x => x } and the input to this function is (myFunc(x)) . In this case, all that the function does is return the input back to the user. Thus if we write { x => x }(1) we will get 1. So we can replace the whole { x => x }(myFunc(x)) with just myFunc(x). What we're left with is

  { x => { x => { x => myFunc(x) }(myFunc(x)) }(myFunc(x)) }

Lets look at the { x => myFunc(x)}(myFunc(x)) term. Here the function part is { x => myFunc(x) } and the input to this function part is given by (myFunc(x)). The function part takes in an integer x and applies myFunc to that integer. It's essentially the same as applying myFunc directly to that integer. In this case, the integer we are applying it to is the input myFunc(x) so we can rewrite { x => myFunc(x) }(myFunc(x)) as myFunc(myFunc(x)). Now we have

   { x => { x => myFunc(myFunc(x)) }(myFunc(x)) }

We can apply the same logic used in the previous step to break down the { x => myFunc(myFunc(x)) }(myFunc(x)) term. We would get myFunc(myFunc(myFunc(x))). If you continue with this logic, you will see that repeater is going to keep composing myFunc. For each n, it will add one more layer of myFunc. The result of this would look like this if n = 3

   { x  => myFunc(myFunc(myFunc((x))) }

Thus for repeater(addOne, 3), we would get

{ x => addOne(addOne(addOne(x))) }

And repeater(addOne, 5) is

{ x => addOne(addOne(addOne(addOne(addOne(x))))) }

All that repeater does it to just constructs this function and return it to the user. You could take this return function of repeater and put in a val called f

 val f = { x => addOne(addOne(addOne(x))) } //ie repeater(addOne, 3)

f takes in an integer input and returns that integer plus 3. We can then get the actual result we want using this

 val someIntegerPlus3: Int = f(someInteger)
2
votes

To make it more understandable I will simplify and desugar some part of your function.

Let's first remove myFunc parameter and replace it with addOne function directly reducing complexity keeping the main question in focus:

def repeater(n:Int): Int => Int = {
   if(n<=0) (x:Int) => x
   else (x: Int) => repeater(n-1)(addOne(x))
}

Now let's desugar function literal instantiation code

def repeater(n:Int): Int => Int = {
  if(n<=0) new Function1[Int,Int]{ //#1
    override def apply(x: Int): Int = x
  }
  else new Function1[Int,Int]{ //#2
    override def apply(x: Int): Int = repeater(n-1)(addOne(x))
  }
}

So now you can see that when you call reporter(2) it produces new function #2 without evaluating it. So at the result you will have something like this:

val repeaterFirstIteration: Int => Int = {
  new Function1[Int,Int]{
    override def apply(x: Int): Int = repeater(2-1)(addOne(x))
  }
}

or let's sugar it back

val repeaterFirstIteration: Int => Int = {
  x => repeater(2-1)(addOne(x))
}

so now you have val containing function literal that you can call like this repeaterFirstIteration(...)