Вступление: Позапрошлым летом я открыл для себя великолепную книгу SICP — чтение только первого раздела книги открыло для меня новый мир функционального программирования. Анонимные функции, функции, что возвращают функции, функции высших порядков. Во втором разделе книги авторы показали, что возможно с помощью одних только функций создавать различные структуры данных, такие как пара, список, или даже деревья! Сегодня мне бы хотелось реализовать кое-какие идеи из этой книги на языке программирования Python. Конечно же, исключительно с помощью функций.
Начало: Python – это замечательный язык программирования, который поддерживает практически все парадигмы программирования. Python прост в понимании, и для чтения этой статьи достаточно базового знания языка. Не будет также лишним немного просмотреть эту статью.
I. Создание пары.Что такое пара?
Пара — это упорядоченный набор, который состоит из двух элементов, предположительно, разных типов. Стоит отметить, что в ЯП Python, кортеж ( пара — это частный случай кортежа) — это особый тип данных, который очень часто используется, и создается следующим образом: p = (a1,a2,..,an). Но так как мы условились использовать только функции, нам придется создать свою собственную реализацию пары:
def make_pair(x,y): return lambda n: x if n==0 else y def first(p): return p(0) def second(p): return p(1) Постойте! Но ведь make_pair возвращает функцию, а не пару. На самом деле – пара в нашем представлении это и есть функция, что принимает на вход аргумент любое число, и возвращает первый элемент, если аргумент равен 0, и второй в противоположном случае. Для повышения уровня абстракции мы также создали функции доступа к элементам нашей пары: first и second. Убедимся, что наша реализация пары работает, как нужно:
p = make_pair(5,6) first(p) #5 second(p) #6 p1 = make_pair('hello',6) first(p1) #'hello' II. Список Что такое список?
Список — это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться более одного раза.
Сейчас мы реализуем связный список — одну из возможных реализаций списка.
Свя́зный спи́сок — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка
На самом деле, связный список можно представить, как пару, которая состоит из двух значений: «голова» списка и его «хвост». К примеру, список [1,2,3,4] можно представить следующим образом:
l = make_pair(1,make_pair(2,make_pair(3,4))) first(l) #1 first(second(l)) #2 Теперь добавим поддержку пустых списков. Пустой список — это список, который не содержит ни одного элемента. При обращении к его элементам, он должен каким-то образом сообщать об ошибке.
def nil(): def closure(n): raise Exception return closure null = nil() first(null) #Exception second(null) #Exception def create_list(x): return make_pair(x,null) К сожалению, функции first и second не являются интуитивно-понятными функциями доступа к элементам списка. Гораздо привычнее работать с функциями head и tail
def head(l): return first(l) def tail(l): return second(l) Здесь стоит вспомнить о том, что в Python функции являются объектами первого класса
Поэтому, код можно значительно упростить:
head = first tail = second Базовой операцией над списком есть добавление нового элемента в голову списка:
def add_to_list(l,x): return make_pair(x,l) Все исключительно просто: мы создаем новый список, «головой» которого будет новый элемент, а «хвостом» — предыдущий список.
Здесь можно остановиться, ведь фактически мы создали полноценный тип данных — список, но, пожалуй, стоит также рассмотреть операции обхода списка.
def iterate_over_list(l,f): if l==null: return else: f(head(l)) iterate_over_list(tail(l),f) Самая простая операция — проход по всем элементам и вызов некоторой функции f к каждому элементу списка. К примеру, с помощью этой функции можно вывести список на экран:
def print_list(l): def put(n): print n iterate_over_list(l,put) l = create_list(5) l =add_to_list(l,6) l = add_to_list(l,7) print_list(l) #7 6 5 Каким образом работает функция iterate_over_list? Она рекурсивно применяет функцию f к голове списка L, пока L не станет равен пустому списку.
Теперь реализуем базовые функциональные операции над списками:
map(l,f) — это функция, которая переводит список в новый список, применяя к его элементам некоторую функцию f.
filter(l,p) — это функция, которая создает новый список, в который попадают только те элементы, которые соответствуют некоторому предикату p.
accumulate(l,op,initial) — более известна, как reduce.
Функция _map работает рекурсивно: если список пуст, то возвращаем пустой список, в противоположном случае возвращаем новый список, «головой» которого будет результат применения функции f к первому элементу списка l, а «хвостом» будет результат применения функции _map к «хвосту» списка l.
def _map(l,f): if null_seq(l): return null else: return make_pair(f(head(l)),_map(tail(l),f)) l = make_list(5) l = add_to_list(l,6) l = add_to_list(l,7) l2 = _map(l,lambda n: n*n) iterate_over_list(l2,pr) # 49 36 25 def _filter(l,p): if null_seq(l): return null else: if p(head(l)): return make_pair(head(l),_filter(tail(l),p)) else: return _filter(tail(l),p) def accumulate(l,op,initial): if null_seq(l): return initial else: return accumulate(tail(l),op,op(initial,head(l))) #вычисление суммы списка с помощью функции accumulate from operator import add _sum = accumulate(l,add,0) И последний штрих — функция range. Если вы дочитали до этого элемента — то наверняка в состоянии реализовать эту функцию самостоятельно.
def create_range(start,end): if start==end: return null else: return make_pair(start,create_range(start+1,end)) l = create_range(0,10) print_list(l) #0 1 2 3 4 5 6 7 8 9
Вместо заключения
Конечно, никто не станет использовать подобные техники в «настоящем» программировании, но я надеюсь, что эта статья все-таки сможет кому-то помочь освоиться в функциональном программировании.
ссылка на оригинал статьи http://habrahabr.ru/post/262021/
Добавить комментарий