MyTetra Share
Делитесь знаниями!
Функциональное программирование / Списки
Время создания: 31.08.2017 21:00
Текстовые метки: knowledge
Раздел: Python - Patterns
Запись: xintrea/mytetra_db_mcold/master/base/15033169502y0804pp41/text.html на raw.githubusercontent.com

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

Python

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



Итак, список. Почему ему придается такое большое значение в мире ФП? Ответ на этот вопрос лежит в концептуальной основе языка 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]



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



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

 
MyTetra Share v.0.60
Яндекс индекс цитирования