Функциональное программирование для землян — списки

Продолжаю свое небольшое введение в функциональное программирование. На этот раз речь пойдет о списках и методах их обработки в функциональном стиле.



Итак, список. Почему ему придается такое большое значение в мире ФП? Ответ на этот вопрос лежит в концептуальной основе языка Lisp. Список (в том или ином виде) является необходимой сематической единицей языка программирования. Без наличия списка мы не сможем получить произвольное количество единиц информации в программе. С другой стороны, добавление только списков позволяет нам реализовать сколь угодно сложные — рекурсивные, даже бесконечные (при наличии в языке поддержки ленивых вычислений) — структуры данных. Список + простые типы данных — тот необходимый минимум, который необходим любому языку программирования. Все остальные сложные типы данных — словари, деревья, графы и т.д. — можно реализовать при помощи списка.

Так решили создатели Lisp… и сделали язык, в котором программы представляют собой список :) Да-да, любая программа на Lisp — суть просто список. Вызов функции — список, в котором первым идет имя функции, а следом — значения аргументов. Определение функции — список, в котором первым идет ключевое слово defun, затем имя функции, затем вложенный список с именами аргументов, затем список операторов. И так далее. На первый взгляд, это кажется довольно глупым и неудобным — многие слышали упреки в сторону Lisp за невероятное количество скобочек (списки там ограничиваются скобочками). Но на второй взгляд… если у программы такая упрощенная синтаксическая структура, то мы вполне можем модифицировать программу непосредственно в рантайме.

И для этого у Lisp есть механизм макросов — функций, результат выполнения которых заново выполняется (наподобие eval в динамических языках программирования, только гораздо гибче). Благодаря механизму макросов Lisp можно изменить до неузнаваемости, можно ввести новый синтаксис и использовать его. Новые операторы (хотели когда-нибудь более удобную форму цикла for? посмотрите на великолепный, гибкий макрос for в Common Lisp — это, не побоюсь сказать, цветок в грубом мире циклов for обычных языков программирования). Своя объектная система, синтаксически встроенная в язык (посмотрите на CLOS — это тоже просто набор макросов, а смотрится в языке как влитая). Вот такая вот гибкость. Хотя, конечно, нужен редактор с подсветкой скобочек — обязательно :)

Теперь вернемся с Lisp к обычным, императивным языкам программирования — что здесь для нас список? Обработка списков (массивов, словарей) также составляет львиную долю программ на Python. Это и обработка выборки данных из БД, и расчет функции для построения, и обработка списка файлов в файловой системе, и обработка списка строк в файле, а также многое, многое другое.

В таких языках мы обычно обрабатываем списки при помощи разного рода циклов — for, while, do...while. Это как бы не является проблемой, но цикл сам по себе не семантичен. Т.е. он не говорит, что конкретно делается со списком. Нам приходится читать код тела цикла и разбирать, что же он делает. ФП в лице Lisp предлагает нам более изящные методы работы со списком (сюда не входят распространенные операции модификации списка — сортировка, обращение, конкатенация и т.п.):

• отображение (map) — к каждому элементу списка применяется некоторая функция, результат которой подставляется вместо этого элемента:
  
  
• фильтрация (filter) — каждый элемент списка проверяется на соответствие функции-предикату, и если элемент не соответствует, он выбрасывается из списка:
  
  
• свертка (reduce) — здесь чуть посложнее. Процесс таков: берется некоторое базовое значение и первый элемент списка и к ним применяется функция-редуктор; затем берется результат действия этой функции и второй элемент списка и к ним снова применяется функция-редуктор; затем снова берется возвращаемое значение функции и третий элемент списка — процесс повторяется до тех пор, пока не закончится список. Результатом свертки будет одно значение. Например, таким образом можно реализовать суммирование всех элементов. Или что-нибудь посложней (например, интерполяцию, или обращение списка). Визуально это можно представить так:
  
  

Обычно к этим трем функциям сводится большинство проблем, связанных с обработкой списков. Но не всегда. Бывает, например левосторонняя и правосторонняя свертка. Бывает необходимость не в фильтрации списка, а в разделении его по некоторому признаку на две части. Да мало ли чего. Суть в том, что есть некая функция, которая на вход принимает список и на выходе выдает либо список, либо какое-то простое значение, не модифицируя при этом исходный список.

В Python вышеописанные функции присутствуют как в виде одноименных функций, так и в виде синтаксического сахара под странным названием list comprehension (не возьмусь корректно перевести, что-то вроде постижение списка).

List comprehensions (LC)

Простейший синтаксис LC таков:

[ expression(a) for a in x ]

где x — список, a — элемент списка, а expression(a) — некоторое выражение, в котором обычно участвует a. LC — это выражение, и его результатом является список. В смысловом плане вышеописанное LC соответствует функции map следующего вида:

map(lambda a: expression(a), x)

Далее, перед самой последней квадратной скобочкой может стоять еще ветка if:

[ expression(a) for a in x if condition(a) ]

Как вы догадались, это аналог filter. При помощи функций мы можем переписать это выражение следующим образом:

map(lambda a: expression(a), 
  filter(lambda a: condition(a), x))

Для reduce синтаксического аналога нет, т.к. основная, первичная цель LC — конструирование списков. Стоит отметить еще один интересный момент: функция map может принимать несколько списков. В этом случае каждый раз при вызове функции-преобразователя ей будет передаваться несколько аргументов: первый аргумент будет значением текущего элемента из первого списка, второй аргумент — значением текущего элемента второго списка и т.д.:

map(
  lambda a1, a2, a3: a1 + a2 + a3, 
  [1, 2, 3], 
  [4, 5, 6], 
  [7, 8, 9])

В LC присутствует, казалось бы, похожая конструкция:

[ expression(a1, a2) for a1 in x1, for a2 in x2 ]

Но, увы, это не то же самое. Результатом действия данной конструкции будет не слишком часто применяемое на практике декартово произведение списков. Для примера:

[ a1 + a2 for a1 in [ 'a', 'b', 'c'] for a2 in ['x', 'y'] ]

=> ['ax', 'ay', 'bx', 'by', 'cx', 'cy']


На практике, LC удобно применять для простых, невложенных операций, вроде получения квадратов чисел от 1 до 10. В иных случаях (см. сложный пример ниже) лучше использовать функции.

Простые примеры

Код ко всем примерам данного поста смотрите ниже. Давайте возьмем список следующего вида:

x = [ 2, 3, 4, 5, 7, 5 ]

Начнем с чего-нибудь простого; например, возведем все элементы списка в квадрат:

map(lambda a: a ** 2, x)

# то же самое, но при помощи LC
[ a ** 2 for a in x ]

=> [4, 9, 16, 25, 49, 25]

Теперь применим фильтрацию — отсеем все четные числа:

filter(lambda a: a % 2 == 1, x)

# то же самое, но при помощи LC
[ a for a in x if a % 2 == 1 ]

=> [3, 5, 7, 5]

Теперь скомбинируем — выведем нечетные квадраты чисел списка:

filter(lambda a: a % 2 == 1, 
  map(lambda a: a ** 2, 
    x))

# то же самое, но при помощи LC
[ a ** 2 for a in x if a ** 2 % 2 == 1 ]

=> [9, 25, 49, 25]

Как видите, в первом случае сначала производим отображение списка, а затем — фильтрацию результата. Теперь поиграем с reduce. Для начала выведем сумму всех чисел списка:

reduce(lambda a, b: a + b, x, 0)

=> 26

Первый параметр, как вы уже поняли, это функция-редуктор (в данном случае, сумматор). Второй параметр — это наш список, и третий — начальное значение, или инициализатор. Чтобы показать важность правильного выбора инициализатора, приведем тот же пример, но для умножения:

reduce(lambda a, b: a * b, x, 0)

=> 0

Здесь мы получили 0. И ведь правильно: получается, выполняется следующее выражение: ((((((0 * 2) * 3) * 4) * 5) * 7) * 5). Исправим этот пример, установив значение инициализатора в единицу:

reduce(lambda a, b: a * b, x, 1)

=> 4200

Теперь мы получим корректное значение. Теперь попробуем получить максимальное значение из списка:

reduce(lambda a, b: max(a, b), x)

=> 7

Здесь уже нет инициализатора. Когда инициализатор не указан, reduce подставляет на его место None. Работу этого кода легче всего пояснить визуально:



И наконец, возьмем задачу обращения списка посредством свертки. Напомню, у нас имеется список чисел 2, 3, 4, 5, 7, 5. Обращенный список будет таков: 5, 7, 5, 4, 3, 2. Давайте расставим скобочки, чтобы увидеть, какую операцию нам нужно будет применить в функции-редукторе: (5, (7, (5, (4, (3, (2)). Очевидно, что это операция добавления каждого нового элемента списка в начало результата с предыдущего шага свертки. Инициализатор же должен быть пустым списком: (5, (7, (5, (4, (3, (2, [])). Теперь запишем конкретный код:

reduce(lambda a, b: [ b ] + a, x, [])

=> [5, 7, 5, 4, 3, 2]

Еще раз, для понятности отобразим визуально:



В этом посте я рассмотрел только простые, «нежизненные» примеры работы со списками, но у меня в запасе есть пример пожизнеспособней, и я его выложу в ближайшее время в новом посте, вместе с некоторыми соображениями по поводу производительности, применимости, о том, какое это находит отражение в других областях компьютерной науки, и вообще. Надеюсь, это будет кому-то интересно. За сим хочу откланяться, спасибо за внимание.