Недавно я начал курс Coursera Functional Programming with Scala (преподаваемый Мартином Одерским — создателем Scala), который фактически служит одновременно введением в FP и Scala, но не раньше. Сам курс великолепен, однако попытка просмотра видео и одновременного использования нового синтаксиса Scala и концепций FP может потребовать некоторых усилий.
Я хотел проработать некоторые основные концепции FP в более знакомом контексте, поэтому собираюсь применить некоторые уроки / принципы / упражнения в Groovy.
Функции:
Если вы выполнили какое-либо программирование на Groovy, вы столкнетесь с функциями / замыканиями Groovy. Поскольку Groovy динамически печатается (по сравнению со статической типизацией Scala), вы можете играть в нее довольно быстро и свободно.
Например, если мы возьмем функцию квадратного корня, которая демонстрируется в курсе Scala, она определяется следующим образом:
def sqrt(x: Double): Double = ...
Как вы можете видеть, Scala ожидает ввода значений (кроме того, на самом деле вам не всегда нужно указывать тип возвращаемого значения в Scala). Но в функции Groovy это:
def sqrt = {x-> ... }
Groovy-функция может быть определена и назначена для любой переменной, что позволяет передавать ее как объект первого класса. Если мы посмотрим на полное решение для вычисления квадратного корня числа (используя метод Ньютона — Чтобы вычислить квадратный корень из «x», мы начнем с оценки квадратного корня «y» и продолжим улучшать предположение путем принимая среднее значение х и х / у)
def sqrtIter(guess: Double, x: Double): Double = if (isGoodEnough(guess, x)) guess else sqrtIter(improve(guess, x), x) def improve(guess: Double, x: Double) = (guess + x / guess) / 2 def isGoodEnough(guess: Double, x: Double) = abs(guess * guess - x) < 0.001 def sqrt(x: Double) = srqtIter(1.0, x)
Так что в Scala, если мы попробуем Groovy, мы увидим, что мы можем легко добиться почти того же:
//Improve the guess using Newton's method
def improve = { guess, x ->
(guess + x / guess) / 2
}
//Check if our guess is good enough, within a chosen threshold
def isGoodEnough = {guess, x ->
abs(guess * guess - x) < 0.001
}
//iterate over guesses until our guess is good enough
def sqrtIter = { guess, x ->
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)
}
//wrap everythin in the square root function call
def sqrt = {x -> srqtIter(1.0, x)}
Рекурсия (и хвостовая рекурсия):
Поскольку FP избегает наличия изменяемого состояния, наиболее распространенный подход к решению проблем состоит в том, чтобы разбить проблему на простые функции и вызывать их рекурсивно. Это позволяет избежать необходимости поддерживать состояние во время итерации через циклы, и каждый вызов функции получает свой ввод и производит выход.
Если мы снова рассмотрим пример из курса Scala, на примере простой функции, которая вычисляет факториал для данного числа.
def factorial ={ n ->
if (n == 0) 1
else n * factorial(n - 1)
}
factorial(4)
Эта простая функция рекурсивно вычисляет факториал, продолжая вызывать себя, пока все числа к нулю не будут учтены. Как вы можете видеть, нет изменяемого состояния — каждый вызов факториальной функции просто принимает входные данные и возвращает выходные данные (значение n никогда не изменяется и не переопределяется, n просто используется для вычисления выходных значений)
Здесь есть проблема, и как только вы попытаетесь вычислить факториал достаточно большого числа, вы столкнетесь с исключением StackOverflow — это происходит потому, что в JVM каждый раз, когда вызывается функция, в кадр добавляется фрейм. стека, поэтому рекурсивная работа довольно проста, чтобы достичь предела стека и столкнуться с этой проблемой. Обычный способ решить эту проблему — использовать рекурсию Tail-Call. Этот трюк состоит в том, чтобы иметь последний код, который оценивается в функции как рекурсивный вызов — обычно на языках FP компилятор / интерпретатор распознает этот шаблон, а на самом деле он просто запускает код как цикл (например, если мы знаем, что самый последний фрагмент кода в блоке кода вызывает сам себя, это на самом деле не так уж и отличается от простого наличия блока кода / функции внутри конструкции цикла)
В предыдущем факториальном примере может показаться, что последний код, который должен быть выполнен, является рекурсивным callfactorial (n-1) — однако значение этого вызова фактически возвращается в функцию и затем умножается на n — так что фактически последний кусок кода, который должен оцениваться при вызове функции, на самом деле является n * возвращаемым значением факториала (n-1).
Давайте посмотрим, как переписать функцию, чтобы она была рекурсивной.
def factorial ={ n, accumulator=1 ->
if (n == 1) accumulator
else factorial(n-1, n*accumulator)
}
factorial(4)
Теперь, используя аккумулятор, последним кодом, который должен быть оценен в функции, является наш рекурсивный вызов функции. В большинстве языков FP, включая Scala, этого достаточно — однако JVM автоматически не поддерживает рекурсию хвостового вызова, поэтому вам действительно нужно использовать более грубый подход в Groovy:
def factorial ={ n, accumulator=1 ->
if (n == 1) accumulator
else factorial.trampoline(n-1, n*accumulator)
}.trampoline()
factorial(4)
Использование метода trampoline () означает, что функция теперь будет вызываться с использованием рекурсии хвостового вызова, поэтому никогда не должно возникать исключение StackOverflow. Это не так хорошо, как в Scala или других языках, но поддержка есть, поэтому мы можем продолжить.
Карринг:
Это похоже на композицию функций — идея заключается в том, что вы берете обобщенную функцию, а затем вы указываете ее на какое-то значение, чтобы сделать более конкретное применение функции. Например, если мы посмотрим на функцию с заданными значениями x и y, она возвращает z, представляющее собой значение x процентов от y (например, учитывая x = 10, y = 100, возвращается 10 процентов от 100, z = 10)
def percentage = { percentage, x ->
x/100 * percentage
}
Вышеприведенная простая функция является общим механизмом для получения процентного значения другого, но если учесть, что мы хотели, чтобы общее применение этой функции заключалось в том, чтобы всегда вычислять 10% заданного значения, а не писать слегка измененную версию функции. мы можем просто карри функцию следующим образом:
def tenPercent = percentage.curry(10)
Теперь, если вызывается функция tenPercent (x), она использует оригинальную функцию процент (), но каррирует значение 10 в качестве первого аргумента. (Если вам нужно каррировать другие позиции аргументов, вы также можете использовать функцию rcurry () для каррирования наиболее правого аргумента или ncurry (), которая также занимает позицию аргумента — для получения дополнительной информации обратитесь к документации Groovy по каррированию).
Неизменность:
Неизменность частично поддерживается в Java обычно с использованием ключевого слова final (то есть переменные не могут быть изменены после первоначальной установки при создании объекта). Groovy также предоставляет быструю и простую аннотацию @Immutable, которую можно добавить в класс, чтобы сделать его неизменным. Но на самом деле, избегать неизменяемого состояния — это больше, чем просто иметь классы как неизменяемые — поскольку у нас есть функции в качестве объектов первого класса, мы можем легко назначать переменные и изменять их внутри функции — так что это скорее ваше мышление или философия чтобы привыкнуть к. Например:
def list = ['groovy', 'functional']
//This mutates the original list
list.add('programming')
//This creates a new list leaving the original unchanged
def newList = list.plus(2, 'programming')
Первый пример, вероятно, больше похож на код на Groovy / Java, который мы привыкли писать, но это изменяет состояние списка — когда второй подход оставляет исходный список неизменным.
Уменьшение карты:
В заключение отметим, что в FP есть некоторые функции, которые являются довольно распространенными методами — наиболее известной из которых в наши дни (отчасти благодаря Google) является Map-Reduce, но трио функций на самом деле Map, Reduce (также известное как Сложите) и Фильтр — вы можете прочитать больше о функциях
здесь (или просто погуглить их!), Но эти функции на самом деле очень хорошо коррелируют с основными функциями Groovy, которые вы, вероятно, часто используете (если вы программисты на Groovy).
карта
Карта является самой легкой для понимания из трех. Он принимает два входа — функцию и список. Затем он применяет эту функцию к каждому элементу в списке. Однако вы можете сделать то же самое с пониманием списка.
Звучит знакомо? Это в основном функция .collect {} в Groovy
Уменьшить / Fold
Это немного сложнее для описания, но это то же самое, что и функция .inject {} в groovy.
Фильтр
И еще один простой способ — отфильтровать список для желаемых элементов, это функция Groovy .findAll {}
Как я уже сказал в начале, я новичок в FP и пришел из OO, но, надеюсь, вышесказанное не так уж далеко от истины! По мере прохождения курса Coursera я попытаюсь опубликовать его снова, возможно, с некоторыми попытками в Groovy, чтобы понять, как это работает.