рекурсивная функция scala, которая возвращает другую функцию - PullRequest
Новая
       25

рекурсивная функция scala, которая возвращает другую функцию

0 голосов
/ 10 апреля 2019

Я смотрел на примеры техники карри в scala и не понимал, как функция может возвращать другую функцию, когда функция рекурсивная.

например, я понимаю этот код 

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))

выше одного для меня, если я скажу, что ретранслятор (addOne, 10, 1) возвращает 11. Пока n равно нулю, я уменьшаю n с 1, и стек рекурсии начинает работать снизу вверх.

Но это меня смущает 

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

Дело в том, что я не понимаю здесь, например, если я запустил ретранслятор (addOne, 2), он будет искать часть else, а часть else говорит, что она возвращает функцию, поэтому программа сначала возвращает функцию или выполняет повторить еще раз с n-1 (1-1) и вернуть другую функцию? Эта другая часть возвращает количество функций и как будет выглядеть стек вызовов?

Ответы [ 3 ]

2 голосов
/ 10 апреля 2019

Чтобы сделать его более понятным, я упросту и поясню некоторую часть вашей функции.

Давайте сначала удалим параметр myFunc и заменим его на функцию addOne, что снизит сложность, оставив основной вопрос в фокусе:

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

Теперь давайте рассмотрим код литерации функции desugar 

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))
  }
}

Итак, теперь вы можете видеть, что когда вы вызываете reporter(2), она генерирует новую функцию #2 без ее оценки.Таким образом, в результате у вас будет что-то вроде этого: 

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

или давайте подсчитаем это обратно 

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

так что теперь у вас есть val содержащий литерал функции, который вы можете вызывать вот такrepeaterFirstIteration(...)

2 голосов
/ 10 апреля 2019

Во-первых, давайте уточним, что если вы запустите repeater(addOne, 3), вы получите только функцию. Вам нужно будет запустить repeater(addOne, 3)(SomeOtherInteger), чтобы получить целочисленное значение и результат ваших вычислений. Все, что здесь делает рекурсия, - это создание функции. repeater(addOne, 3) возвращает функцию, которая принимает целое число и возвращает целое число. Возьмите пример repeater(addOne, 3), если мы полностью запишем результат рекурсии, это то, что мы получим 

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

Это может показаться немного запутанным, но давайте разберемся с этим.

Позволяет сосредоточиться на самой внутренней части - { x => x }(myFunc(x)). Это может быть разделено на две части, функцию и вход в функцию. Функция { x => x } и вход для этой функции (myFunc(x)). В этом случае все, что делает функция, это возвращает ввод обратно пользователю. Таким образом, если мы напишем { x => x }(1), мы получим 1. Таким образом, мы можем заменить все { x => x }(myFunc(x)) просто myFunc(x). То, что у нас осталось, это 

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

Давайте посмотрим на { x => myFunc(x)}(myFunc(x)) термин. Здесь функциональной частью является { x => myFunc(x) }, а вход для этой функциональной части задается (myFunc(x)). Часть функции принимает целое число x и применяет myFunc к этому целому числу. По сути, это то же самое, что применение myFunc непосредственно к этому целому числу. В этом случае целое число, к которому мы его применяем, является вводом myFunc(x), поэтому мы можем переписать { x => myFunc(x) }(myFunc(x)) как myFunc(myFunc(x)). Теперь у нас есть 

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

Мы можем применить ту же логику, которая использовалась на предыдущем шаге, чтобы разбить термин { x => myFunc(myFunc(x)) }(myFunc(x)). Мы бы получили myFunc(myFunc(myFunc(x))). Если вы продолжите эту логику, вы увидите, что repeater будет составлять myFunc. Для каждого n будет добавлен еще один слой myFunc. Результат будет выглядеть так, если n = 3

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

Таким образом, для repeater(addOne, 3) мы бы получили 

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

А repeater(addOne, 5) составляет 

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

Все, что repeater делает, просто создает эту функцию и возвращает ее пользователю. Вы можете взять эту функцию возврата repeater и вставить val с именем f

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

f принимает целочисленный ввод и возвращает это целое число плюс 3. Затем мы можем получить фактический результат, который мы хотим, используя это 

 val someIntegerPlus3: Int = f(someInteger)
2 голосов
/ 10 апреля 2019

Давайте развернем рекурсию шаг за шагом.

repeater(addOne, 2) возвращает новую анонимную функцию 

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

Где repeater(addOne, 1) возвращает новую анонимную функцию 

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

Где repeater(addOne, 0) возвращает новую анонимную функцию 

(x:Int) => x

Поэтому repeater(addOne, 1) возвращает анонимную функцию, которая выглядит как 

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

И repeater(addOne, 2) возвращает анонимную функцию, которая выглядит как 

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