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



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

Комментарии (9)


  1. lair
    07.07.2015 19:08

    def _map(l,f):
        if null_seq(l):
            return null
        else:
            return make_pair(f(head(l)),_map(tail(l),f))
    

    Что будет, если в списке 500 элементов? Десять тысяч? Миллион?


    1. Monnoroch
      07.07.2015 19:53

      Будет очень плохо.
      Питон для этого не предназначен. На самом деле, список в том же хаскеле — это интерфейс навроде генератора. Не надо его использовать в качестве хранилища. А без ленивости это полный трэш.


    1. phantomit Автор
      08.07.2015 00:10

      До меня уже написали, что «Все будет очень плохо». От себя еще могу добавить, что если в CPython была бы поддержка хвостовой рекурсии «из коробки», я бы написал _map (да и остальные функции) иначе.
      Впрочем, в Python есть свои решения для поддержки TCO.


      1. lair
        08.07.2015 00:12

        Ну так может быть об этом надо написать в статье, потому как это типовая для функциональных языков проблема?


        1. gbezyuk
          08.07.2015 03:56

          Это не «типовая проблема функциональных языков», это очевидная проблема масштабирования данной «лабораторной» реализации. То есть по сути это «проблема микроскопа» в ситуации забивания им гвоздей.


  1. SirEdvin
    07.07.2015 22:58
    +1

    Немного LISP в Python?


  1. knagaev
    08.07.2015 14:30

    Не знаю, известно ли вам, что теперь этот курс (SICP) читают на Python, но на всякий случай вот ссылка на материалы
    www-inst.eecs.berkeley.edu/~cs61a/fa11/61a-python/content/www/index.html
    Надеюсь, поможет в освоении SICP на Python :)


    1. phantomit Автор
      08.07.2015 14:49

      Спасибо за ссылку, не видел ранее этот курс. Просмотрел примеры — код какой-то совсем императивный.

      def sum_naturals(n):
       """Sum the first n natural numbers.
       >>> sum_naturals(5)
       15
       """
       total, k = 0, 1
       while k <= n:
        total, k = total + k, k + 1
       return total
      


      1. knagaev
        08.07.2015 15:11

        А вы по какому признаку отличаете императивный код от декларативного? :)
        В приведенном примере ведь простая итерация.
        В функциональных языках итерации тоже можно использовать.
        Там дальше как раз идёт описание работы с higher-order functions, и такой код совсем не мешает.

        Это просто пример, скорректированный к синтаксису Python.
        Вы наверняка сами уже оценили, что SICP рассказывает идеи, а имплементировать можно на любых языках, которые позволяют (например, поддерживают эти самые HOF).