Элементы функционального программирования

Списковые включения

Для более естественной записи обработки списков в Python 2 была внесена новинка: списковые включения. Фактически это специальный сокращенный синтаксис для вложенных циклов for и условий if, на самом низком уровне которых определенное выражение добавляется к списку, например:

all_pairs = []
for i in range(5):
  for j in range(5):
    if i <= j:
      all_pairs.append((i, j))

Все это можно записать в виде спискового включения так:

all_pairs = [(i, j) for i in range(5) for j in range(5) if i <= j]

Как легко заметить, списковые включения позволяют заменить map() и filter() на более удобные для прочтения конструкции.

В следующей таблице приведены эквивалентные выражения в разных формах:

Функция sum()

Получить сумму элементов можно с помощью функции sum():

>>> sum(range(10))
45

Эта функция работает только для числовых типов, она не может конкатенировать строки. Для конкатенации списка строк следует использовать метод join().

Функция reduce()

Для организации цепочечных вычислений (вычислений с накоплением результата) можно применять функцию reduce(), которая принимает три аргумента: функцию двух аргументов, последовательность и начальное значение. С помощью этой функции можно, в частности, реализовать функцию sum():

def sum(lst, start):
  return reduce(lambda x, y: x + y, lst, start)

В следующем примере накапливаются промежуточные результаты суммирования:

lst = range(10)
f = lambda x, y: (x[0] + y, x[1]+[x[0] + y])
print reduce(f, lst, (0, []))

В итоге получается:

(45, [0, 1, 3, 6, 10, 15, 21, 28, 36, 45])

Функция zip()

Эта функция возвращает список кортежей, в котором i -й кортеж содержит i -е элементы аргументов-последовательностей. Длина результирующей последовательности равна длине самой короткой из последовательностей-аргументов:

>>> print zip(range(5), "abcde")
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]

Итераторы

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

Итераторы можно применять вместо последовательности в операторе for. Более того, внутренне оператор for запрашивает от последовательности ее итератор. Объект файлового типа тоже (построчный) итератор, что позволяет обрабатывать большие файлы, не считывая их целиком в память.

Там, где требуется итератор, можно использовать последовательность.

Работа с итераторами рассматривается в разделе, посвященном функциональному программированию, так как итераторами удобно манипулировать именно в функциональном стиле.

Использовать итератор можно и "вручную". Любой объект, поддерживающий интерфейс итератора, имеет метод next(), который при каждом вызове выдает очередное значение итератора. Если больше значений нет, возбуждается исключение StopIteration. Для получения итератора по некоторому объекту необходимо прежде применить к этому объекту функцию iter() (цикл for делает это автоматически).

В Python имеется модуль itertools, который содержит набор функций, комбинируя которые, можно составлять достаточно сложные схемы обработки данных с помощью итераторов. Далее рассматриваются некоторые функции этого модуля.

Функция iter()

Эта функция имеет два варианта использования. В первом она принимает всего один аргумент, который должен "уметь" предоставлять свой итератор. Во втором один из аргументов - функция без аргументов, другой - стоповое значение. Итератор вызывает указанную функцию до тех пор, пока та не возвратит стоповое значение. Второй вариант встречается много реже первого и обычно внутри метода класса, так как сложно порождать значения "на пустом месте":

it1 = iter([1, 2, 3, 4, 5])

def forit(mystate=[]):
  if len(mystate) < 3:
    mystate.append(" ")
    return " "

it2 = iter(forit, None) 

print [x for x in it1]
print [x for x in it2]

Функция enumerate()

Эта функция создает итератор, нумерующий элементы другого итератора. Результирующий итератор выдает кортежи, в которых первый элемент - номер (начиная с нуля), а второй - элемент исходной последовательности:

>>> print [x for x in enumerate("abcd")]
[(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd')]

Функция sorted()

Эта функция, появившаяся в Python 2.4, позволяет создавать итератор, выполняющий сортировку:

>>> sorted('avdsdf')
['a', 'd', 'd', 'f', 's', 'v']

Далее рассматриваются функции модуля itertools.

Функция itertools.chain()

Функция chain() позволяет сделать итератор, состоящий из нескольких соединенных последовательно итераторов. Итераторы задаются в виде отдельных аргументов. Пример:

from itertools import chain
it1 = iter([1,2,3])
it2 = iter([8,9,0])
for i in chain(it1, it2):
    print i,

даст в результате

1 2 3 8 9 0

Функция itertools.repeat()

Функция repeat() строит итератор, повторяющий некоторый объект заданное количество раз:

for i in itertools.repeat(1, 4): 
    print i,

1 1 1 1

Функция itertools.count()

Бесконечный итератор, дающий целые числа, начиная с заданного:

for i in itertools.count(1):
    print i,
    if i > 100:
        break

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
96 97 98 99 100 101

Функция itertools.cycle()

Можно бесконечно повторять и некоторую последовательность (или значения другого итератора) с помощью функции cycle():

tango = [1, 2, 3]
for i in itertools.cycle(tango):
    print i,

1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2
3 1 2 3 1
2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
1 2 3 1 2
3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 . . .

Функции itertools.imap(), itertools.starmap() и itertools.ifilter()

Аналогами map() и filter() в модуле itertools являются imap() и ifilter(). Отличие imap() от map() в том, что вместо значения от преждевременно завершившихся итераторов объект None не подставляется. Пример:

for i in map(lambda x, y: (x,y), [1,2], [1,2,3]):
    print i,

(1, 1) (2, 2) (None, 3)

from itertools import imap
for i in imap(lambda x, y: (x,y), [1,2], [1,2,3]):
  print i,

(1, 1) (2, 2)

Здесь следует заметить, что обычная функция map() нормально воспринимает итераторы в любом сочетании с итерабельными (поддающимися итерациям) объектами:

for i in map(lambda x, y: (x,y), iter([1,2]), [1,2,3]):
    print i,

(1, 1) (2, 2) (None, 3)

Функция itertools.starmap() подобна itertools.imap(), но имеет всего два аргумента. Второй аргумент - последовательность кортежей, каждый кортеж которой задает набор параметров для функции (первого аргумента):

>>> from itertools import starmap
>>> for i in starmap(lambda x, y: str(x) + y, [(1,'a'), (2,'b')]):
...   print i,
...
1a 2b

Функция ifilter() работает как filter(). Кроме того, в модуле itertools есть функция ifilterfalse(), которая как бы добавляет отрицание к значению функции:

for i in ifilterfalse(lambda x: x > 0, [1, -2, 3, -3]): 
    print i,

-2 -3

Функции itertools.takewhile() и itertools.dropwhile()

Некоторую новизну вносит другой вид фильтра: takewhile() и его "отрицательный" аналог dropwhile(). Следующий пример поясняет их принцип действия:

for i in takewhile(lambda x: x > 0, [1, -2, 3, -3]):
    print i,

print 
for i in dropwhile(lambda x: x > 0, [1, -2, 3, -3]):
  print i,

1 -2 3 -3

Таким образом, takewhile() дает значения, пока условие истинно, а остальные значения даже не берет из итератора (именно не берет, а не высасывает все до конца!). И, наоборот, dropwhile() ничего не выдает, пока выполняется условие, зато потом выдает все без остатка.

Функция itertools.izip()

Функция izip() аналогична встроенной zip(), но не тратит много памяти на построение списка кортежей, так как итератор выдает их строго по требованию.

Функция itertools.groupby()

Эта функция дебютировала в Python 2.4. Функция принимает два аргумента: итератор (обязательный) и необязательный аргумент - функцию, дающую значение ключа: groupby(iterable[, func]). Результатом является итератор, который возвращает двухэлементный кортеж: ключ и итератор по идущим подряд элементам с этим ключом. Если второй аргумент опущен, элемент итератора сам является ключом. В следующем примере группируются идущие подряд положительные и отрицательные элементы:

import itertools, math
lst = map(lambda x: math.sin(x*.4), range(30))
for k, i in itertools.groupby(lst, lambda x: x > 0):
  print k, list(i);

Функция itertools.tee()

Эта функция тоже появилась в Python 2.4. Она позволяет клонировать итераторы. Первый аргумент - итератор, подлежащий клонированию. Второй ( N ) -- количество необходимых копий. Функция возвращает кортеж из N итераторов. По умолчанию N=2. Функция имеет смысл, только если итераторы задействованы более или менее параллельно. В противном случае выгоднее превратить исходный итератор в список.

Собственный итератор

Для полноты описания здесь представлен пример итератора, определенного пользователем. Если пример не очень понятен, можно вернуться к нему после изучения объектно-ориентированного программирования:

class Fibonacci:
  """Итератор последовательности Фибоначчи до N"""

  def __init__(self, N): 
    self.n, self.a, self.b, self.max = 0, 0, 1, N

  def __iter__(self): 
    # сами себе итератор: в классе есть метод next() 
    return self

  def next(self):
    if self.n < self.max:
      a, self.n, self.a, self.b = self.a, self.n+1, self.b, self.a+self.b
      return a
    else: 
      raise StopIteration

# Использование:  
for i in Fibonacci(100):
  print i,

Простые генераторы

Разработчики языка не остановились на итераторах. Как оказалось, в интерпретаторе Python достаточно просто реализовать простые генераторы. Под этим термином фактически понимается специальный объект, вычисления в котором продолжаются до выработки очередного значения, а затем приостанавливаются до возникновения необходимости в выдаче следующего значения. Простой генератор формируется функцией-генератором, которая синтаксически похожа на обычную функцию, но использует специальный оператор yield для выдачи следующего значения. При вызове такая функция ничего не вычисляет, а создает объект с интерфейсом итератора для получения значений. Другими словами, если функция должна возвращать последовательность, из нее довольно просто сделать генератор, который будет функционально эквивалентной "ленивой" реализацией. Ленивыми называются вычисления, которые откладываются до самого последнего момента, когда получаемое в результате значение сразу используется в другом вычислении.

Для примера с последовательностью Фибоначчи можно построить такой вот генератор:

def Fib(N):
  a, b = 0, 1
  for i in xrange(N):
    yield a
    a, b = b, a + b

Использовать его не сложнее, чем любой другой итератор:

for i in Fib(100):
  print i,

Однако следует заметить, что программа в значительной степени упростилась.

Генераторное выражение

В Python 2.4 по аналогии со списковым включением появилось генераторное выражение. По синтаксису оно аналогично списковому, но вместо квадратных скобок используются круглые. Списковое включение порождает список, а, значит, можно ненароком занять очень много памяти. Генератор же, получающийся в результате применения генераторного выражения, списка не создает, он вычисляет каждое следующее значение строго по требованию (при вызове метода next() ).

В следующем примере можно прочесть из файла строки, в которых производятся некоторые замены:

for line in (l.replace("- ", " - ") for l in open("input.dat")):
  print line

Ничто не мешает использовать итераторы и для записи в файл:

open("output.dat", "w").writelines(
        l.replace("- ", " - ") for l in open("input.dat"))

Здесь для генераторного выражения не потребовалось дополнительных скобок, так как оно расположено внутри скобок вызова функции.

Карринг

Библиотека Xoltar toolkit (автор Bryn Keller) включает модуль .

При карринге (частичном применении) функции создается новая функция, задавая некоторые аргументы исходной. Следующий пример иллюстрирует частичное применение вычитания:

from functional import curry
def subtract(x, y):
    return x - y

print subtract(3, 2)
subtract_from_3 = curry(subtract, 3)
print subtract_from_3(2)
print curry(subtract, 3)(2)

Во всех трех случаях будет выведено 1. В следующем примере получается новая функция, подставляя второй аргумент. Вместо другого аргумента вставляется специальное значение Blank:

from functional import curry, Blank
def subtract(x, y):
    return x - y

print subtract(3, 2)
subtract_2 = curry(subtract, Blank, 2)
print subtract_2(3)
print curry(subtract, Blank, 2)(3)

Заключение

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

Следует отметить, что итераторы - это практичное продолжение функционального начала в языке Python. Итераторы по сути позволяют организовать так называемые ленивые вычисления (lazy computations), при которых значения вычисляются только когда они непосредственно требуются.

Ссылки по теме

Статья Д. Мертца http://www-106.ibm.com/developerworks/library/l-prog.html

Часто задаваемые вопросы в comp.lang.functional http://www.cs.nott.ac.uk/~gmh/faq.html