Свертка
Похоже, я переживаю вторую волну функционализации мышления :) Первая была в 93-94гг, когда нам в школе объяснили LISP, и мы на нем делали всякие задания. Например, калькулятор рекурсивным спуском. Отголоском был годом позже спецкурс для студентов третьего курса, куда я будучи еще зеленым первокурсником храбро ходил, хотя и не все тогда получалось. В то время функциональные языки были не в почете, и рассматривались сугубо из академического интереса. Но за прошедшие 16 лет многое изменилось: железо стало мощным, интерпретаторы и компиляторы умными, и появилась возможность разрабатывать эффективные приложения в том числе и на функциональных языках. Народ вовсю программирует серьезные приложения на функциональных Ruby, F#, Haskell, Scala. Популярность функциональных языков вдохновляется в том числе и новыми задачами, стоящими перед программистами сегодня, и которые сложно или неудобно решать в императивном стиле.
С языком Scala меня познакомил года два назад коллега, который использует его для научной работы. У Скалы есть одно огромное преимущество перед другими функциональными языками: Скала интероперабельна с мега-популярным языком программирования Java, то есть в программе на Скале можно использовать джавовские классы и библиотеки, программа компилируется в байт-код JVM, можно использовать джавские веб-контейнеры и сервера-приложений, среды разработки и т.п. Это не просто огромное, это для практической работы просто ОГРОМНОЕ преимущество. Несмотря на некоторое сопротивление, мы запустили один проект на Скале, и я его с большим удовольствием развиваю.
Так в чем же заключается функционализация мышления? В первую очередь, это не использование функций, как можно было бы подумать, а предпочтение immutable, то есть не изменяемых, объектов. Никаких i = i+1. Immutable объекты делают программы a priori более стабильными и удобными в отладке (к слову, я в Скале вообще ни разу не использовал отладчик), и заставляют использовать функциональные приемы обработки данных.
После такого длинного вступления, я коротко и максимально "на кастрюльках" расскажу об одном приеме, пример которого я уже приводил в посте про язык J. Тогда я его еще не очень распробовал, и только недавно по-настоящему оценил, как он помогает сделать программы еще более компактными и избавиться от ненужных циклов. Речь идет о функции высшего порядка fold. На русский это можно перевести, наверное, как "свертка". Существует две модификации этой функции: foldLeft и foldRight. Они отличаются порядком применения, но для простоты ограничимся "левой" версией.
В посте про J, я приводил пример вычисления факториала. Вернемся к нему еще раз, разбив для простоты на две строчки.
val x = List.range(1,N) /* определение списка от 1 до N */
val f = (1/:x)(_*_)
На самом деле '/:' это синтаксическое упрощение, которое несколько прячет суть. Его можно переписать несколько по-другому:
val f = (x foldLeft 1)(_*_)
или еще более подробно:
val f = (x foldLeft 1)( (a,b) => a*b)
Теперь я попытаюсь объяснить, что это значит. Сначала синтаксически. В Скале выражения (x f y) интерпретируются как x.f(y), то есть (x foldLeft 1) это вызов функции у объекта x с параметром 1. Но скобки дальше указывают, что результат вызова первой части -- это функция со сложным параметром. В свою очередь ( (a,b) => a*b) -- это функция, которая перемножает два аргумента. То есть прочитаем все выражение: вызвать у объекта x метод foldLeft с параметром 1 и потом вызвать результат с параметром-функцией, перемножающей свои аргументы. Не слабо, да? Вообще-то все не совсем так, но так, мне кажется, проще объяснить.
Теперь, что же делает foldLeft? Он для каждого элемента списка x, начиная слева, применяет бинарную функцию, переданную во втором параметре, к этому элементу и промежуточному результату. Для первого элемента списка результат -- начальное значение -- первый параметр. То есть сначала будет перемножена 1 и первый элемент списка, то есть тоже 1, потом результат будет перемножен на следующий элемент списка, то есть 2, и т.д. Поэтому для списка (1,2,3,4,5), будет выполнена такая последовательность:
((((1*1)*2)*3)*4)*5
Или это еще можно представить следующим наглядным образом:
(List(1,2,3,4,5) foldLeft 1)( (a,b) => a*b)
(List(2,3,4,5) foldLeft 1*1)( (a,b) => a*b)
(List(3,4,5) foldLeft 1*1*2)( (a,b) => a*b)
(List(4,5) foldLeft 1*1*2*3)( (a,b) => a*b)
(List(5) foldLeft 1*1*2*3*4*5)( (a,b) => a*b)
(List() foldLeft 1*1*2*3*4*5)( (a,b) => a*b)
1*1*2*3*4*5
Результат как бы "перетекает" из одной части в другую. Это очень мощный механизм. Помимо всяких агрегаторных целей, он может использоваться и для нетривиального преобразования объектов (тривиальные делаются через другую функцию высшего порядка -- map). Например, обращение списка:
val reverse = (x foldLeft List[Int]())((a,b) => b :: a)
В общем случае:
def foldLeft [B] (z: B)(f: (B, A) ⇒ B) : B
Обычно вместо четырех строчек кода получается одна. Действительно, эквивалент на императивном языке мог бы выглядеть примерно так:
var a=z
for (i<-x)
a = f(a,i)
return a
И на самом деле, не только из-за fold, но и из-за использования других функций высших порядков, программы на Скале получаются в среднем в 3-4 раза короче эквивалентных программ на Джаве, ни сколько не теряя, но приобретая при этом в читаемости. При некотором навыке, конечно.
Резюмирую, что свертка -- это универсальный принцип функционального программирования, который позволяет сворачивать громоздкие программы к чистую математическую мысль.
С языком Scala меня познакомил года два назад коллега, который использует его для научной работы. У Скалы есть одно огромное преимущество перед другими функциональными языками: Скала интероперабельна с мега-популярным языком программирования Java, то есть в программе на Скале можно использовать джавовские классы и библиотеки, программа компилируется в байт-код JVM, можно использовать джавские веб-контейнеры и сервера-приложений, среды разработки и т.п. Это не просто огромное, это для практической работы просто ОГРОМНОЕ преимущество. Несмотря на некоторое сопротивление, мы запустили один проект на Скале, и я его с большим удовольствием развиваю.
Так в чем же заключается функционализация мышления? В первую очередь, это не использование функций, как можно было бы подумать, а предпочтение immutable, то есть не изменяемых, объектов. Никаких i = i+1. Immutable объекты делают программы a priori более стабильными и удобными в отладке (к слову, я в Скале вообще ни разу не использовал отладчик), и заставляют использовать функциональные приемы обработки данных.
После такого длинного вступления, я коротко и максимально "на кастрюльках" расскажу об одном приеме, пример которого я уже приводил в посте про язык J. Тогда я его еще не очень распробовал, и только недавно по-настоящему оценил, как он помогает сделать программы еще более компактными и избавиться от ненужных циклов. Речь идет о функции высшего порядка fold. На русский это можно перевести, наверное, как "свертка". Существует две модификации этой функции: foldLeft и foldRight. Они отличаются порядком применения, но для простоты ограничимся "левой" версией.
В посте про J, я приводил пример вычисления факториала. Вернемся к нему еще раз, разбив для простоты на две строчки.
val x = List.range(1,N) /* определение списка от 1 до N */
val f = (1/:x)(_*_)
На самом деле '/:' это синтаксическое упрощение, которое несколько прячет суть. Его можно переписать несколько по-другому:
val f = (x foldLeft 1)(_*_)
или еще более подробно:
val f = (x foldLeft 1)( (a,b) => a*b)
Теперь я попытаюсь объяснить, что это значит. Сначала синтаксически. В Скале выражения (x f y) интерпретируются как x.f(y), то есть (x foldLeft 1) это вызов функции у объекта x с параметром 1. Но скобки дальше указывают, что результат вызова первой части -- это функция со сложным параметром. В свою очередь ( (a,b) => a*b) -- это функция, которая перемножает два аргумента. То есть прочитаем все выражение: вызвать у объекта x метод foldLeft с параметром 1 и потом вызвать результат с параметром-функцией, перемножающей свои аргументы. Не слабо, да? Вообще-то все не совсем так, но так, мне кажется, проще объяснить.
Теперь, что же делает foldLeft? Он для каждого элемента списка x, начиная слева, применяет бинарную функцию, переданную во втором параметре, к этому элементу и промежуточному результату. Для первого элемента списка результат -- начальное значение -- первый параметр. То есть сначала будет перемножена 1 и первый элемент списка, то есть тоже 1, потом результат будет перемножен на следующий элемент списка, то есть 2, и т.д. Поэтому для списка (1,2,3,4,5), будет выполнена такая последовательность:
((((1*1)*2)*3)*4)*5
Или это еще можно представить следующим наглядным образом:
(List(1,2,3,4,5) foldLeft 1)( (a,b) => a*b)
(List(2,3,4,5) foldLeft 1*1)( (a,b) => a*b)
(List(3,4,5) foldLeft 1*1*2)( (a,b) => a*b)
(List(4,5) foldLeft 1*1*2*3)( (a,b) => a*b)
(List(5) foldLeft 1*1*2*3*4*5)( (a,b) => a*b)
(List() foldLeft 1*1*2*3*4*5)( (a,b) => a*b)
1*1*2*3*4*5
Результат как бы "перетекает" из одной части в другую. Это очень мощный механизм. Помимо всяких агрегаторных целей, он может использоваться и для нетривиального преобразования объектов (тривиальные делаются через другую функцию высшего порядка -- map). Например, обращение списка:
val reverse = (x foldLeft List[Int]())((a,b) => b :: a)
В общем случае:
def foldLeft [B] (z: B)(f: (B, A) ⇒ B) : B
Обычно вместо четырех строчек кода получается одна. Действительно, эквивалент на императивном языке мог бы выглядеть примерно так:
var a=z
for (i<-x)
a = f(a,i)
return a
И на самом деле, не только из-за fold, но и из-за использования других функций высших порядков, программы на Скале получаются в среднем в 3-4 раза короче эквивалентных программ на Джаве, ни сколько не теряя, но приобретая при этом в читаемости. При некотором навыке, конечно.
Резюмирую, что свертка -- это универсальный принцип функционального программирования, который позволяет сворачивать громоздкие программы к чистую математическую мысль.