Функциональное программирование на Python. Часть 1. Общие вопросы
Функциональное программирование является интересной парадигмой, которая поможет по-новому взглянуть на процесс разработки и, несомненно, расширит ваш опыт новыми идеями и подходами.
Парадигмы программирования
Для начала обратимся к википедии за определением понятия “парадигма программирования”. Парадигма программирования — это совокупность идей и понятий, определяющих стиль написания компьютерных программ (подход к программированию). Это способ концептуализации, определяющий организацию вычислений и структурирование работы, выполняемой компьютером.
Императивное программирование предполагает ответ на вопрос “Как?”. В рамках этой парадигмы вы задаете последовательность действий, которые нужно выполнить, для того чтобы получить результат. Результат выполнения сохраняется в ячейках памяти, к которым можно обратиться в последствии.
Декларативное программирование предполагает ответ на вопрос “Что?”. Здесь вы описываете задачу, даете спецификацию, говорите, что вы хотите получить в результате выполнения программы, но не определяете, как этот ответ будет получен.
Каждая из этих парадигм включает в себя более специфические модели. В промышленности наибольшее распространение получили структурное и объектно-ориентированное программирование из группы “императивное программирование” и функциональное программирование из группы “декларативное программирование”.
Довольно часто бывает так, что дизайн языка позволяет использовать все перечисленные парадигмы (например Python ) или только часть из них (например, C++ ).
В чем суть функционального программирования?
Языки, которые можно отнести в функциональной парадигме обладают определенным набором свойств. Если язык не является чисто функциональным, но реализует эти свойства, то на нем можно разрабатывать, как говорят, в функциональном стиле. Свойства функционального стиля программирования:
Python не является функциональным языком программирования, но его возможностей хватает, чтобы разрабатывать программы в функциональном стиле.
Примеры работы в функциональном стиле
Функции, как объекты первого класса
Рекурсия
Рекурсия – это вызов функции из нее же самой. Для начала приведем пример не рекурсивной функции, которая считает факториал:
В качестве результата получим число 120.
Перепишем ее через рекурсию:
Результат получим аналогичный первому. Заметим, что такая реализация не является эффективной по памяти, о том почему это так, и как сделать правильно см “О рекурсии и итерации“
Функции высшего порядка
Чистые функции
Чистые функции – это функции, которые не имеют побочных эффектов. В Python это не выполняется. Необходимо самостоятельно следить за тем, чтобы функция была чистой.
Например, следующая функция модифицирует данные, которые в нее передаются:
P.S.
Мир Python: функционалим по-маленьку — Python для продвинутых
Введение
Существует несколько парадигм в программировании, например, ООП, функциональная, императивная, логическая, да много их. Мы будем говорить про функциональное программирование.
Предпосылками для полноценного функционального программирования в Python являются: функции высших порядков, развитые средства обработки списков, рекурсия, возможность организации ленивых вычислений.
Сегодня познакомимся с простыми элементами, а сложные конструкции будут в других уроках.
Теория в теории
Как и в разговоре об ООП, так и о функциональном программировании, мы стараемся избегать определений. Все-таки четкое определение дать тяжело, поэтому здесь четкого определения не будет. Однако! Хотелки для функционального языка выделим:
Это не полный список, но даже этого хватает чтобы сделать «красиво». Если читателю хочется больше, то вот расширенный список:
Постепенно рассмотрим все эти моменты и как использовать в Python.
А сегодня кратко, что есть что в первом списке.
Чистые функции
Чистые функции не производят никаких наблюдаемых побочных эффектов, только возвращают результат. Не меняют глобальных переменных, ничего никуда не посылают и не печатают, не трогают объектов, и так далее. Принимают данные, что-то вычисляют, учитывая только аргументы, и возвращают новые данные.
Неизменяемые данные
Преимущества неизменяемых структур:
Функции высшего порядка
Функцию, принимающую другую функцию в качестве аргумента и/или возвращающую другую функцию, называют функцией высшего порядка:
Рассмотрели теорию, начнем переходить к практике, от простого к сложному.
Списковые включения или генератор списка
Рассмотрим одну конструкцию языка, которая поможет сократить количество строк кода. Не редко уровень программиста на Python можно определить с помощью этой конструкции.
Цикл с условием, подобные встречаются не редко. А теперь попробуем эти 5 строк превратить в одну:
В общем виде эта конструкция такова:
Стоит понимать, что если код совсем не читаем, то лучше отказаться от такой конструкции.
Анонимные функции или lambda
Продолжаем сокращать количества кода.
Функция короткая, а как минимум 2 строки потратили. Можно ли сократить такие маленькие функции? А может не оформлять в виде функций? Ведь, не всегда хочется плодить лишние функции в модуле. А если функция занимает одну строчку, то и подавно. Поэтому в языках программирования встречаются анонимные функции, которые не имеют названия.
Анонимные функции в Python реализуются с помощью лямбда-исчисления и выглядят как лямбда-выражения:
Для программиста это такие же функции и с ними можно также работать.
Чтобы обращаться к анонимным функциям несколько раз, присваиваем переменной и пользуемся на здоровье.
Лямбда-функции могут выступать в качестве аргумента. Даже для других лямбд:
Использование lambda
Функция map() обрабатывает одну или несколько последовательностей с помощью заданной функции.
Мы уже познакомились с генератором списков, давайте им воспользуемся, если длина списков одинаковая:
Итак, заметно, что использование списковых включений короче, но лямбды более гибкие. Пойдем дальше.
filter()
Функция filter() позволяет фильтровать значения последовательности. В результирующем списке только те значения, для которых значение функции для элемента истинно:
То же самое с помощью списковых выражений:
reduce()
Для организации цепочечных вычислений в списке можно использовать функцию reduce(). Например, произведение элементов списка может быть вычислено так (Python 2):
Вычисления происходят в следующем порядке:
Цепочка вызовов связывается с помощью промежуточного результата (res). Если список пустой, просто используется третий параметр (в случае произведения нуля множителей это 1):
Разумеется, промежуточный результат необязательно число. Это может быть любой другой тип данных, в том числе и список. Следующий пример показывает реверс списка:
Для наиболее распространенных операций в Python есть встроенные функции:
В Python 3 встроенной функции reduce() нет, но её можно найти в модуле functools.
apply()
Функция для применения другой функции к позиционным и именованным аргументам, заданным списком и словарем соответственно (Python 2):
В Python 3 вместо функции apply() следует использовать специальный синтаксис:
На этой встроенной функции закончим обзор стандартной библиотеки и перейдем к последнему на сегодня функциональному подходу.
Замыкания
Функции, определяемые внутри других функций, представляют собой замыкания. Зачем это нужно? Рассмотрим пример, который объяснит:
Что можно в коде заметить: в этом коде переменные, которые живут по сути постоянно (т.е. одинаковые), но при этом мы загружаем или инициализируем по несколько раз. В итоге приходит понимание, что инициализация переменной занимает львиную долю времени в этом процессе, бывает что даже загрузка переменных в scope уменьшает производительность. Чтобы уменьшить накладные расходы необходимо использовать замыкания.
В замыкании однажды инициализируются переменные, которые затем без накладных расходов можно использовать.
Научимся оформлять замыкания:
Заключение
В уроке мы рассмотрели базовые понятия ФП, а также составили список механизмов, которые будут рассмотрены в следующих уроках. Поговорили о способах уменьшения количества кода, таких как cписковые включения (генератор списка), lamda функции и их использовании и на последок было несколько слов про замыкания и для чего они нужны.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты.
Нашли опечатку или неточность?
Выделите текст, нажмите ctrl + enter и отправьте его нам. В течение нескольких дней мы исправим ошибку или улучшим формулировку.
Что-то не получается или материал кажется сложным?
Загляните в раздел «Обсуждение»:
Об обучении на Хекслете
Открыть доступ
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно.
Функциональное программирование на Python
Рассмотрена поддержка функционального программирования в языке Python. Даны примеры использования лямбда-выражений и функций высших порядков
Парадигма функционального программирования
В отличие от императивного, которое работает со строго определёнными состояниями и инструкциями, функциональное программирование основывается на взаимодействии с функциями, то есть процессами, описывающими связь между входными и выходными параметрами. Таким образом, в то время, как императивный язык описывает конкретное действие с известными входными параметрами, функциональный описывает некое тело взаимодействий, не опускаясь до конкретных случаев.
Функциональное программирование, несмотря на кажущуюся сложность, несёт в себе ряд преимуществ:
— Код становится короче;
— Включает в себя признаки императивных языков: модульность, типизация, чистота кода.
Примерами функциональных языков являются LISP (Clojure), Haskell, Scala, R.
Функциональное программирование, как и логическое программирование, нашло большое применение в теории искусственного интеллекта и её приложениях.
В основном, языки программирования представляют собой гибрид нескольких парадигм программирования, в частности, одни из таких языков является Python. Однако можно выделить основные концепции функционального программирования:
Чистые функции
Это концепция является основной в функциональном программировании. Чистые функции удовлетворяют двум условиям:
1. Функция, вызываемая от одних и тех же аргументов, всегда возвращает одинаковое значение. Например, если происходит вызов функции sum(2, 3), то ожидается, что результат всегда будет равен 5. При вызове же функции rand(), или при обращении к переменной, не определённой в функции, чистота функции нарушается, а это в функциональном программировании недопустимо.
Функции высших порядков.
Рекурсия.
В функциональных языках цикл обычно реализуется в виде рекурсии, так как в функциональной парадигме программирования отсутствует такое понятия, как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.
Переменные неизменяемы.
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только создавать новые путём разбора и сбора существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря этому в чистых функциональных языках все функции свободны от побочных эффектов.
Лямбда-исчислении
2. При вызове все функции проходят процесс каррирования. Он заключается в следующем: если вызывается функция с несколькими аргументами, то сперва она будет выполнена лишь с первым аргументом и вернёт новую функцию, содержащую на 1 аргумент меньше, которая будет немедленно вызвана. Этот процесс рекурсивен и продолжается до тех пор, пока не будут применены все аргументы, возвращая финальный результат. Поскольку функции являются чистыми, это работает.
Краткая история функционального программирования
Теория так и оставалась теорией, пока в конце 1950-х годов Джон Маккарти не разработал язык Лисп, который стал первым почти функциональным языком программирования и многие годы оставался единственным таковым. Лисп всё ещё используется (также как и Фортран), после многих лет эволюции он удовлетворяет современным запросам, которые заставляют разработчиков программ взваливать как можно большую ношу на компилятор, облегчив так свой труд. Нужда в этом возникла из-за всё более возрастающей сложности программного обеспечения.
В связи с этим обстоятельством всё большую роль начинает играть типизация. В конце 70-х — начале 80-х годов XX века интенсивно разрабатываются модели типизации, подходящие для функциональных языков. Большинство этих моделей включали в себя поддержку таких мощных механизмов как абстракция данных и полиморфизм. Появляется множество типизированных функциональных языков: ML, Scheme, Hope, Miranda, Clean и многие другие. Вдобавок постоянно увеличивается число диалектов.
В семидесятых в университете Эдинбурга Робин Милнер создал язык ML, а Дэвид Тернер начинал разработку языка SASL в университете Сент-Эндрюса и, впоследствии, язык Miranda в университете города Кент. В конечном итоге на основе ML были созданы несколько языков, среди которых наиболее известные Objective Caml и Standard ML. Также в семидесятых осуществлялась разработка языка программирования, построенного по принципу Scheme (реализация не только функциональной парадигмы), получившего описание в известной работе «Lambda Papers», а также в книге восемьдесят пятого года «Structure and Interpretation of Computer Programs».
В результате вышло так, что практически каждая группа, занимающаяся функциональным программированием, использовала собственный язык. Это препятствовало дальнейшему распространению этих языков и порождало многие более мелкие проблемы. Чтобы исправить положение, объединённая группа ведущих исследователей в области функционального программирования решила воссоздать достоинства различных языков в новом универсальном функциональном языке. Первая реализация этого языка, названного Haskell в честь Хаскелла Карри, была создана в начале 90-х годов.
Большинство функциональных языков программирования реализуются как интерпретируемые, следуя традициям Лиспа (примечание: большая часть современных реализаций Лиспа содержат компиляторы в машинный код). Таковые удобны для быстрой отладки программ, исключая длительную фазу компиляции, укорачивая обычный цикл разработки. С другой стороны, интерпретаторы в сравнении с компиляторами обычно проигрывают по скорости выполнения. Поэтому помимо интерпретаторов существуют и компиляторы, генерирующие машинный код (например, Objective Caml) или код на С/С++ (например, Glasgow Haskell Compiler). Практически каждый компилятор с функционального языка реализован на этом же самом языке. Это же характерно и для современных реализаций Лиспа, кроме того среда разработки Лиспа позволяет выполнять компиляцию отдельных частей программы без остановки программы (вплоть до добавления методов и изменения определений классов).
Особенности функционального программирования
Основной особенностью функционального программирования, определяющей как преимущества, так и недостатки данной концепции, является то, что в ней реализуется модель вычислений без состояний. Если императивная программа на любом этапе исполнения имеет состояние, то есть совокупность значений всех переменных, и производит побочные эффекты, то чисто функциональная программа ни целиком, ни частями состояния не имеет и побочных эффектов не производит. То, что в императивных языках делается путём присваивания значений переменным, в функциональных достигается путём передачи выражений в параметры функций. Непосредственным следствием становится то, что чисто функциональная программа не может изменять уже имеющиеся у неё данные, а может лишь создавать новые путём копирования или расширения старых. Следствием этого является отказ от циклов в пользу рекурсии.
Достоинства функционального программирования:
Недостатки функционального программирования::
Недостатки функционального программирования следуют из его плюсов. Отсутствие присваиваний и замена их на создание новых данных приводят к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональной программы обязательным компонентом становится высокоэффективный сборщик мусора. Нестрогая модель вычислений приводит к непредсказуемому порядку вызова функций, что создает проблемы при вводе-выводе, где порядок выполнения операций важен. Кроме того, функции ввода в своем естественном виде (например, getchar из стандартной библиотеки языка C) не являются чистыми, поскольку способны возвращать различные значения для одних и тех же аргументов, и для устранения этого требуются определенные ухищрения.
Для преодоления недостатков функциональных программ уже первые языки функционального программирования включали не только чисто функциональные средства, но и механизмы императивного программирования. Использование таких средств позволяет решить некоторые практические проблемы, но означает отход от идей функционального программирования и написание императивных программ на функциональных языках.
Поддержка функционального программирования в Python
Python поддерживает большую часть характеристик функционального программирования, начиная с версии Python 1.0. Но, как и большинство возможностей Python, они присутствуют в очень смешанном языке.
Функции в Python
Функции в Python определяются 2-мя способами: через определение def или через анонимное описание lambda. Оба этих способа определения доступны, в той или иной степени, и в некоторых других языках программирования. Особенностью Python является то, что функция является таким же именованным объектом, как и любой другой объект некоторого типа данных, например, как целочисленная переменная. В листинге представлен пример объявления одной и той же функции разными способами:
При вызове всех трёх объектов-функций мы получим один и тот же результат:
Введите число: 13
< class ‘function’ > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
< class ‘function’ > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
< class ‘function’ > : < function pow3 at 0x03425270 >
arg = 13.0 => fun(arg) = 2197.0
В Python версии 3, в которой всё является классами (в том числе, и целочисленная переменная), функции являются объектами программы, принадлежащими к классу function.
Если функциональные объекты Python являются такими же объектами, как и другие объекты данных, значит, с ними можно и делать всё то, что можно делать с любыми данными:
— динамически изменять в ходе выполнения;
— встраивать в более сложные структуры данных (коллекции);
— передавать в качестве параметров и возвращаемых значений и т.д.
На этом (манипуляции с функциональными объектами как с объектами данных) и базируется функциональное программирование. Python, конечно, не является настоящим языком функционального программирования, так, для полностью функционального программирования существуют специальные языки: Lisp, Planner, а из более свежих: Scala, Haskell. Ocaml. Но в Python можно «встраивать» приёмы функционального программирования в общий поток императивного (командного) кода, например, использовать методы, заимствованные из полноценных функциональных языков. Т.е. «сворачивать» отдельные фрагменты императивного кода (иногда достаточно большого объёма) в функциональные выражения.
Основным преимуществом функционального программирования является то, что после однократной отладки такого фрагмента в нём при последующем многократном использовании не возникнут ошибки за счёт побочных эффектов, связанных с присвоениями и конфликтом имён.
Достаточно часто при программировании на Python используют типичные конструкции из области функционального программирования, например:
В результате запуска получаем:
Элементы функционального программировании в Python
Основными элементами функционального программирования в Python являются следующие функции: lambda, map, filter, reduce, zip.
lambda выражение
lambda оператор или lambda функция в Python это способ создать анонимную функцию, то есть функцию без имени. Такие функции можно назвать одноразовыми, они используются только при создании. Как правило, lambda функции используются в комбинации с функциями filter, map, reduce.
Синтаксис lambda выражения в Python:
В качестве arguments передается список аргументов, разделенных запятой, после чего над переданными аргументами выполняется expression. Если присвоить lambda-функцию переменной, то получим поведение как в обычной функции:
Но все преимущества lambda-выражений состоят в использовании lambda в связке с другими функциями.
Ниже приведен пример использования lambda-выражения который позволяет напечатать словарь в порядке убывания суммы каждого значения:
На выводе получим отсортированный словарь в виде списка:
Кроме того, можно создавать списки lambda-выражений, которые позволяют получить список действий, выполняемых по требованию:
Также можно создавать таблицы действий с помощью словарей, значениями которых являются lambda-выражения:
Функция map()
Тот же эффект мы можем получить, применив функцию map:
В результате запуска получим тоже самое:
Такой способ занимает меньше строк, более читабелен и выполняется быстрее. map также работает и с функциями, созданными пользователем:
А теперь то же самое, только используя lambda выражение:
Функция map может быть так же применена для нескольких списков, в таком случае функция-аргумент должна принимать количество аргументов, соответствующее количеству списков:
Если же количество элементов в списках совпадать не будет, то выполнение закончится на минимальном списке:
Функция filter()
Функция filter предлагает элегантный вариант фильтрации элементов последовательности. Принимает в качестве аргументов функцию и последовательность, которую необходимо отфильтровать:
Функция, передаваемая в filter должна возвращать значение True или False, чтобы элементы корректно отфильтровались.
Функция reduce()
Функция reduce принимает 2 аргумента: функцию и последовательность. reduce() последовательно применяет функцию-аргумент к элементам списка, возвращает единичное значение.
Вычисление суммы всех элементов списка при помощи reduce:
Вычисление наибольшего элемента в списке при помощи reduce:
Функция zip()
Функция zip объединяет в кортежи элементы из последовательностей переданных в качестве аргументов.
Функция zip прекращает выполнение, как только достигнут конец самого короткого списка.
Замыкание в Python
Смысл замыкания состоит в том, что определение функции «замораживает» окружающий её контекст на момент определения. Это может делаться различными способами, например, за счёт параметризации создания функции, как показано:
Вот как срабатывает такая динамически определённая функция:
Никакие последующие присвоения значений параметру по умолчанию не приведут к изменению ранее определённой функции, но сама функция может быть переопределена.
Частичное применение функции
Сравнение замыкания, частичного определения и функтора:
Вызов всех трёх конструкций для аргумента, равного 5, приведёт к получению одинакового результата, хотя при этом и будут использоваться абсолютно разные механизмы:
Карринг
Это преобразование было введено М. Шейнфинкелем и Г. Фреге и получило своё название в честь математика Хаскелла Карри, в честь которого также назван и язык программирования Haskell.
Карринг не относится к уникальным особенностям функционального программирования, так карринговое преобразование может быть записано, например, и на языках Perl или C++. Оператор каррирования даже встроен в некоторые языки программирования (ML, Haskell), что позволяет многоместные функции приводить к каррированному представлению. Но все языки, поддерживающие замыкания, позволяют записывать каррированные функции, и Python не является исключением в этом плане.
В листинге 8 представлен пример с использованием карринга:
Вот как выглядит результат этих вызовов:
Таким образом, поддержка функционального программирования в Python реализована достаточно полно, хотя и понятно, что Python не является чистым функциональным языком.
Литература
6. Харрисон Д. Введение в функциональное программирование