Python
January 2009 21

Функциональное программирование для землян — функции



В статье про Python пользователь Xronos попросил рассказать о функциональном программировании (ФП). Поскольку я одно время довольно плотно занимался с Lisp, я хотел бы немножко рассказать об этом. Сразу хочу сказать, что о чистом ФП речь не идет. Я расскажу о более простых и более применимых приемах на примере языка Python.



Сразу скажу, почему я не буду рассказывать о чистом ФП. Чистое ФП подразумевает отсутствие состояния вычисления и немодифицируемость памяти (отсутствие побочных эффектов выполнения подпрограмм). Грубо говоря, вся программа в чистом ФП представляет собой одну большую формулу. Чисто императивные концепции, вроде последовательности вычислений, ввода-вывода и изменяемого состояния, в них реализуются различными красивыми способами вроде монад в Haskell. Кроме того, в ФП включают различные концепции более высокого порядка:

  • совпадение по шаблону (pattern matching) — наподобие перегрузки функций, только более продуманно и более гибко
  • продолжения (continuation) — возможность останавливать вычисление и продолжать его в другое время (т.е. «консервировать» состояние вычисления и потом возобновлять его). Вид продолжения мы видим в работе оператора yield
  • ленивые вычисления — При такой модели, грубо говоря, аргументы функций вычисляются только тогда, когда они реально необходимы, а не при входе в функцию
  • алгебраические типы данных, рекурсивные типы данных, автоматический вывод типов — и т.д. и т.п.


На этом я концентрироваться не буду, поскольку а) сам не применял этих концепций на практике (или применял, но ограниченно), б) их применимость для «обычного» программиста на «обычных» языках пока недоступна. Поэтому мы начнем с более простых понятий.

Функции



В ФП все завязано вокруг функций, поэтому функция должна быть объектом первого рода (first-class object). Это значит, что функцию можно создать (анонимная функция), можно присвоить переменной, можно передать в функцию, можно вернуть из функции. Вновь созданные функции должны обладать свойством замыкания (closure) — т.е. новая функция должна захватывать окружающий контекст (объявленные переменные как локальной, так и глобальной области видимости). Простой пример (полный код к данному посту вы можете найти по ссылкам внизу поста):

# encoding: utf-8
def get_writer(type, params):
  # вывод данных в HTML
  def html_writer(filename):
    f = open(filename + '.' + type, 'w');
    f.write("""
<html>
  <head>
    <title>%s</title>
  </head>
  <body>
    <h1>Hello</h1>
  </body>
""" % params['title'])
    f.close()
  # вывод данных в PLAIN TEXT
  def text_writer(filename):
    f = open(filename + '.' + type, 'w');
    f.write("""
%s
=================================

Hello
""")
    f.close()
  # определим, какой тип данных запросили, и вернем соответсвующую функцию
  if type == 'html':
    return html_writer
  elif type == 'txt':
    return text_writer

params = { 'title': 'Header' }

# выведем в HTML
f = get_writer('html', params)
f('file1')
# выведем в PLAIN TEXT
f = get_writer('txt', params)
f('file2')


Обратите внимание на то, что внутри html_writer и text_writer используются аргументы get_writer (type и params). Как такое может быть? Ведь после возврата из get_writer ее аргументы, по идее, перестают существовать? В этом и заключается суть замыкания: если одна функция возвращает другую, то к последней добавляется еще и так называемый контекст — совокупность всех доступных переменных (локальных, глобальных, аргументов) с их значениями на момент вызова. Таким образом, при возврате функции из функции вы возвращаете не просто функцию (простите за тавталогию), а замыкание — функцию + контекст.

Функции высшего порядка



Теперь представьте такой пример. Мы пишем программу построения графиков определенных функций. Определим пару таких функций:

# encoding: utf-8
import math

# y = k * x + b
def get_linear(k, b):
  return lambda x: k * x + b

# y = k * x^2 + b

def get_sqr(k, b):
  return lambda x: k * x ** 2 + b

# y = A * sin(k * x + phi)
def get_sin(amplitude, phi, k):
  return lambda x: amplitude * math.sin(math.radians(k * x  + phi))

# y = A * e^(k*x)
def get_exp(amplitude, k, b):
  return lambda x: amplitude * math.exp(k * x + b)


Это простые функции. Как мы можем их использовать:

# y = 5 * sin(0.3 * x + 30)
y = get_sin(5, 30, 0.3)

# y(90) = 4.19
print y(90)
print
# результат применения y к интервалу от 0 до 180
print [ y(x) for x in range(0, 180) ]


Но, вы видите, каждая из этих функций поддерживает операцию сдвига функции по оси X. А ведь это отдельная функция и мы можем ее выделить! И точно так же мы можем выделить функции масштабирования по X и по Y:

def shifter(func, b):
  return lambda x: func(x + b)

def x_scaler(func, k):
  return lambda x: func(k*x)

def y_scaler(func, A):
  return lambda x: A * func(x)

def combine(func1, func2):
  return lambda x: func2(func1(x))


shifter, x_scaler, y_scaler, combine — это функции высшего порядка (high-order functions), т.к. они принимают не только скалярные аргументы, но и другие функции, модифицируя их поведение. Combine — крайне полезная общая функция, позволяющая применить одну функцию к другой. Теперь мы можем переписать наши предыдущие функции следующим образом:

def identity(x):
  return x

def sqr(x):
  return x ** 2


Уже интересней. Мы переименовали две функции, а две вообще убрали. Зачем переименовали? Дело в том, что избавившись от «шелухи» вроде масштабирования и переноса, мы получили еще более общие функции. Первая из них называется identity — функция идентичности — очень важное понятие в ФП. Очень важное, но очень простое — возвращает свой аргумент и все. Вторая функция просто возводит аргумент в квадрат. Теперь любую конфигурацию, которую мы могли описать нашими функциями из первого примера, мы можем получить путем комбинирования простых функций и функций высшего порядка — главное комбинировать их в корректной последовательности. Для демонстрации того, что значит в корректной последовательности, приведу такое выражение:

y = x_scaler(shifter(x_scaler(sqr, 5), 6), 7)


Какую результирующую функцию мы получим? Сначала к аргументу применяется… нет, не x_scaler(5) и не sqr, а самый внешний x_scaler. Затем shifter. затем внутренний x_scaler. Затем sqr. Покрутите это немного у себя в голове, к этому нужно немного «привыкнуть». Порядок такой: первым применяется самый внешний модификатор. Результат будет полностью аналогичен следующей функции:

def y(x):
  return sqr(((x * 7) + 6) * 5)


С тем различием лишь, что мы фактически создали эту функцию вручную по кусочкам. Теперь давайте для закрепления попробуем написать y = 5 * sin(0.3 * x + 30):

# самым последним должен применяться y_scaler(5)
y = y_scaler(math.sin, 5)
# предпоследним -- превращение угла в радианы
y = combine(math.radians, y)
# далее -- shifter(30)
y = shifter(y, 30)
# наконец -- x_scaler(0.3)
y = x_scaler(y, 0.3)


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

И последний финт функциями



Поднаторев в комбинировании, мы довольно просто напишем, например, модулятор одной функции при помощи другой:

def modulate(mod, src):
  return lambda x: mod(x) * src(x)


Теперь мы можем описать затухающие гармонические колебания:

# y1 = 5 * sin(15 * x + 30) -- исходная функция
y1 = \
  x_scaler(
    shifter(
      combine(
        math.radians,
        y_scaler(
          math.sin, 
          5)), 
      30), 
  15)

# y2 = exp(-0.01 * x) -- модулирующая функция
y2 = x_scaler(math.exp, -0.01)

y = modulate(y2, y1)

print [ y(x) for x in range(0, 180) ]


По-моему, неплохо:



На этом, пожалуй, пост закончу. В следующий раз будут списки, техника map-reduce и list comprehensions как синтаксический сахар для данной техники и как это все помогает нам более ясно выражать свои мысли в коде.

Код к этому посту: 1 2 3 4

UPDATE: т.к. кармы теперь достаточно, решил перенести этот топик в блог Python
+67
7.1k 100
Comments 26
Top of the day