[Из песочницы] Создание простейших структур данных с помощью функций в Python
Вступление: Позапрошлым летом я открыл для себя великолепную книгу 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
Вместо заключения
Конечно, никто не станет использовать подобные техники в «настоящем» программировании, но я надеюсь, что эта статья все-таки сможет кому-то помочь освоиться в функциональном программировании.
