http://habrahabr.ru/post/262021/

Вступление: Позапрошлым летом я открыл для себя великолепную книгу 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. Если вы дочитали до этого элемента — то наверняка в состоянии реализовать эту функцию самостоятельно.


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