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

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



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


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



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

    Подробнее
    Реклама
    Комментарии 42
    • 0
      Хм, введение в функциональное программирование на Python? Не лучше ли для этой цели использовать функциональные языки, например Scheme? Там и лямбда вычисления лучше продемонстрировать можно, и pattern matching показать. Python все таки не функциональный язык.
      • +2
        Прочитал первую часть и понял почему Python:).
      • +1
        ваш перевод термина list comprehensions совем бессмысленный. варианты с включением, вложением, добавлением и охватом гораздо лучше раскрывают его значение
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            мне больше нравиться вариант «описание списков», чем по сути и является этот «сахарок»
            • НЛО прилетело и опубликовало эту надпись здесь
              • 0
                собственно, я нигде не предлагал его переводить, но раз уж речь зашла о том, как это звучит на русском, то осмелился предложить свой вариант, который скорее не дословный, а ближе по смыслу. в данном случае, «описание списка» подразумевает наличие спискового/списочного литерала ([ ]) и заключённого в него «описания» элементов списка. соглашаться с моим мнением никого не обязываю)

                кстати, генераторы в питоне — это отдельная история, хотя можно согласиться, что выражение в скобках как бы «генерирует» элементы списка

                а книга, случайно, не на русском?
                • НЛО прилетело и опубликовало эту надпись здесь
                  • +2
                    Не-а, квадратные скобки во втором питоне — это не генератор, это именно сборка или что-то в таком духе.

                    >>> ( a + b for a, b in (('a', 'b'), ('a', 'b')) )
                    <generator object at 0xb7bff54c>
                    >>> [ a + b for a, b in (('a', 'b'), ('a', 'b')) ]
                    ['ab', 'ab']
                    • 0
                      >>> ( a + b for a, b in (('a', 'b'), ('a', 'b')) )
                      <generator object at 0xb7bff54c>

                      ничего себе, век живи век учись. Первый раз такую конструкцию вижу, спасибо.
                      • +1
                        Если не ошибаюсь, начиная с 2.4 такая возможность есть.
                        В 3.0 «[...]», насколько знаю, уже будет возвращать настоящие генераторы вместо списков, но пока 3.0 не сильно распространён.
                        • 0
                          [] — это по сути конструктор списка. В 3.х в этом плане он работает так же как и в 2.х.
                          Кстати допускается еще такая запись:
                          >>> def f(a):
                          ...     return a
                          ... 
                          >>> f(i for i in '123')
                          <generator object at 0xec7638>
                          

                      • 0
                        ну а где у меня сказано, что квадратные скобки — это генератор? тем более, что я отдельно упомянул питоновские генераторы. я всего лишь считаю, что list comprehensions — это элемент декларативного программирования в питоне, т.е. это выражение описывает список, его элементы, и пытаюсь это растолковать.
                        • 0
                          Я и не говорю, что вы ошиблись, наоборот, подтверждаю ваше мнение, что называть «[...]» генератором лучше не стоит во избежание путаницы.
                          • 0
                            ну да, учитывая, что термин «генератор списков» в оригинальном издании использовался для пояснения, а не в качестве перевода)
                        • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  по-моему, это как раз та ситуация, когда перевод только усугубляет :) Наверное, лучше не переводить вовсе, а использовать «приблизительный» термин — такой как вы придумали, «описание списков», мне кажется вполне нормальным.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      как я ответил выше, я никому не навязываю такой перевод, но и «генераторы списков» мне тоже не очень нравятся. более того, я не сторонник переводов всего и вся на русский, не смотря на то, что это родной язык, и даже более однозначные термины тоже предпочитаю в оригинальном варианте. вобще, по-моему, стоит оставить этот термин в покое, важнее понимать, что он значит, а не как переводится.
                • 0
                  А мне понравилось :) Спасибо, коллега, позволил себе продолжить тему работы со списками при помощи итераторов. Ну и плюс вам, естественно!
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • +1
                        Спасибо за статью.
                        Но мне интересно, насколько часто используются функциональная парадигма в реальных программах на питоне (а не примерах)? Потому что даже в данной статье сказано, что «в более сложных случаях, лучше использовать функции». И к тому же, я часто слышал упреки в более плохой читаемости кода в случае частого использования map(), reduce(), list comprehension. И у меня, откровенно говоря, складывается впечатление, что в питоне (и именно в питоне) функциональное программирование годится в основном для примеров, или каких-то чисто академических задач.
                        Интересно, что серьезные программисты на питоне об этом думают?
                        • 0
                          Внимательнее прочтите последний абзац. Обещают выложить «примеры пожизненнее»
                          • +1
                            > насколько часто используются функциональная парадигма в реальных программах на питоне (а не примерах)?

                            Ну, насколько часто используется структурная парадигма в ваших программах? Сколько процентов занимает в них ООП? Нужно понимать, что это тоже инструмент, который можно применять совместно с другими подходами. Вы используете map, filter или reduce? Или list comprehensions? Или генераторы (которые по сути являются continuations)? Если да, то вы уже использовали кусочки того, что мы называем «функциональным подходом».

                            > в более сложных случаях, лучше использовать функции
                            • +1
                              недоответил, сорри.

                              > в более сложных случаях, лучше использовать функции

                              вы немного неправильно поняли эту фразу. Я имел в виду, что в более сложных случаях лучше использовать функции map, filter и reduce вместо list comprehensions :) Почему — потому что LC имеют свойство «теряться» в синтаксисе; слишком уж незначительны для нашего програмистского взгляда квадратные скобочки.

                              > И к тому же, я часто слышал упреки в более плохой читаемости кода в случае частого использования map(), reduce()

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

                                x = \
                                  # filter something out
                                  filter(lambda a: ...,
                                    # convert something to something else
                                    map(lambda a: ...,
                                       # filter other odd things
                                       filter(someNamedFunction,
                                          ....
                                          data_entries)))))
                              


                              Насколько яснее может выглядеть программа? :) Отступы нам показывают вложенность, последовательность операций читается сразу же, разве нет? Вы начинаете с самой вложенной операции и поднимаетесь вверх — и видите весь алгоритм.
                              • 0
                                Код можно сделать плохо читаемым и самыми «простыми» средствами, например, вложенными циклами :)

                                Если применять вышеперечисленные структуры без фанатизма, проблем не возникает и код становиться более компактным. Можно посмотреть стандартные библиотеки, там не так много, но есть. Зато часто используется lambd'ы и замыкания для отложенных вычислений. Соответственно, используются функции высшего порядка.
                                • 0
                                  Пара примеров из реально работающего и используемого в проектах кода. Отправка уведомлений для всем админам в системе:
                                  def notify_admins(msg):
                                      map(lambda x: x.message_set.create(message=msg),
                                          User.objects.filter(is_staff=True))


                                  А вот пример поэзотеричнее:
                                  def handle_noargs(self, **kwargs):
                                          map(unlink, reduce(lambda x,y: x+y, (x for x in [[join(d,f) for f in fs if f.endswith('.pyc') or f.endswith('.pyo')] for d,_,fs in walk('.')] if x)))


                                  Кто первым скажет, то эта функция делает — плюс в карму :-D
                                  • 0
                                    Удаляет все файлы с расширением pyc или pyo в текущей директории и всех поддиректориях?
                                    • 0
                                      Ага :)
                                      • 0
                                        Кстати, я так ни за что бы не написал :-) Читать неудобно, так что раскидал бы на переменные, а вместо map использовал бы цикл.
                                        • 0
                                          Ну, я бы тоже так, пожалуй не стал бы писать. Но из песни слов не выкинешь, как говорится. Этот код не моему перу принадлежит — это я из репозитория взял первое, что попалось. Просили же иллюстрацию.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • +1
                                        Ну говнокод бывает разный: есть былокодерский говнокод, а есть говнокод, написанный просветленным человеком. Говнокод плохо читаем, но первый тип — из-за того, что его автор ваще не втыкает, что пишет, а во втором случае — из-за того, что автор находится на недостижимом для большинства уровне сознания. :-D Я бы эту кодятину отнес, скорее, ко второй категории, но так писать в коммерческих разработках, конечно, не очень хорошо.
                                  • 0
                                    Отличная статья, спасибо!
                                    • 0
                                      А не будет ли конструкция

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

                                      слишком «жирной»? При применении редуктора к каждому элементу x всё-таки новый список генерируется… Насколько лучше (и лучше ли) будет вариант с простым циклом?

                                      b=[]
                                      for a in x: b.insert(0, a)
                                      • 0
                                        Да, будет гораздо медленней. Этим примером я просто хотел показать, что результат reduce — не обязательно одно значение (т.к. reduce чаще всего применяется именно для свертки списка в одно значение тем или иным способом), но может быть и список, например.

                                        На практике я, конечно, просто сделаю x.reverse()
                                        • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Кстати, использовать LC в случае

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

                                        тоже можно, если использовать функцию zip

                                        [a1 + a2 + a3 for a1, a2, a3 in zip([1, 2, 3], [4, 5, 6], [7, 8, 9])]
                                        • 0
                                          А reduce в 3.0 убрали из встроенных функциях, мотивируя это тем, что его аналог в виде for нагляднее.
                                          • 0
                                            Мда. Не могу сказать, что это меня радует. Ну, по крайней мере, его можно вызывать из модуля functools…
                                          • +1
                                            В LC присутствует, казалось бы, похожая конструкция:
                                            [ expression(a1, a2) for a1 in x1, for a2 in x2 ]
                                            Но, увы, это не то же самое.


                                            >>> [ a + b for a, b in ('a', 'b'), ('a', 'b') ]
                                            ['ab', 'ab']

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.