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

Аннотация: В статье обсуждается роль оператора композиции функций и его левого и правого сечения при программировании на языке Haskell в так называемом «бесточечном» стиле. Показано, что разнообразные композиции функции нескольких аргументов с функцией одного аргумента единообразно выражаются через последовательности таких сечений.

We discuss the function composition operator and its left and right sections in point-free style Haskell programming. We show that the variety of compositions of unary and n-ary functions are expressible as a sequence of such sections.

Обсуждение статьи ведётся по адресу
http://community.livejournal.com/fprog/8243.html.

1  Введение

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

Программирование на прикладных функциональных языках представляет собой некоторый компромисс между этими крайностями. Бесточечный стиль программирования тяготеет к комбинаторной логике. Для него зачастую характерна удивительная краткость записи. Многие, однако, жалуются на низкую читабельность программ записанных в этом стиле. Хотя некоторую часть таких претензий можно признать обоснованными, тем не менее во многих ситуациях бесточечная запись может ясно и лаконично выразить мысль программиста [2, 3].

Бесточечный стиль программирования уже обсуждался на страницах журнала [5]. Напомним, что первое систематическое описание такого подхода к программированию дано в знаменитой лекции Джона Бэкуса «Can programming be liberated from the Von Neumann style?» [1]. На практике, помимо Haskell, бесточечный стиль используют в языках семейства ML и в наследниках APL — языках J и K.

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

Здесь стоит отметить, что в статье мы используем термин «функция n аргументов» для фактического обозначения функции n или большего числа аргументов. Для Haskell такой подход вполне допустим, поскольку «лишние» аргументы можно «спрятать» с помощью частичного применения функции. Например, утверждение, что функция zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] требует функции двух аргументов в качестве своего первого аргумента, не может рассматриваться как запрет на вызов zipWith (\ x y z -> x - y + z). Хотя лямбда-функция здесь явно задана как функция трёх аргументов (её тип Int -> Int -> Int -> Int), но в данном вызове она используется как функция двух аргументов с типом Int -> Int -> (Int -> Int).

Также следует отметить, что мы будем использовать символ равенства = как для определения функций, так и для выражения эквивалентности двух конструкций, допустимых в синтаксисе Haskell. Обычно тип такого использования будет оговариваться, если только он не ясен из контекста.

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

2  Бесточечный стиль: сечения и композиция

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

в бесточечном стиле мы пишем

Такое отбрасывание аргументов допустимо, только если самый правый аргумент в левой части является самым правым и в правой части (и при этом больше нигде в правой не используется). В нашем примере это аргумент xs.

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

Прочитав это определение в обратную сторону, легко увидеть, что у нас есть способ «вытащить» аргумент x из скобок. Например, для

преобразования, использующие это определение,

позволяют перейти к эквивалентному бесточечному определению

Проиллюстрированный этим примером метод перехода от аппликаций к композиции является одним из основных при построении бесточечных определений функций. Именно поэтому для бесточечного стиля характерно очень широкое использование оператора композиции.

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

перемножает (product) первые три элемента списка (take 3), предварительно увеличенных на единицу (map succ):

Бесточечное программирование возможно не только для функций, но и для операторов. Специфика бесточечного стиля для операторов связана с понятием сечений, обсуждавшемся, например, в [5]. Например, для функции

«частично» бесточечная¹ версия

базируется на эквивалентности

Скобки здесь обязательны, поскольку именно они задают левое сечение оператора сложения.

Чтобы продолжить освобождение от аргументов, можно выполнить следующие эквивалентные преобразования

позволяющие перейти к полностью бесточечному определению

Преобразование (1) базируется на возможности записать любой оператор в функциональной форме, заключив его в скобки. Преобразование (2) основано на переходе к правому сечению оператора умножения. Наконец, преобразование (3) демонстрирует использование определения оператора композиции функций ( . ) для «протаскивания» переменной min через правую скобку.

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

3  Левое сечение композиции

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

Легко увидеть общий паттерн: для произвольной функции

тип левого сечения композиции имеет вид

или, эквивалентно,

Можно сформулировать это так: сечение (f . ) преобразует переданную в качестве аргумента функцию g :: l -> a в функцию g' :: l -> b; это превращение происходит с помощью функции f :: a -> b:

Описанное превращение удобно изображать с помощью диаграмм. При этом исходную функцию (g) будем изображать на диаграммах обычной стрелкой, результирующую (g') — стрелкой из точек, а вспомогательную f — волнистой стрелкой:

Можно сформулировать наше наблюдение с меньшей степенью формализма: тип сечения (f . ) :: (l -> a) -> (l -> b) получается приписыванием стрелочки (l ->) слева (отсюда и использование типовой переменной l — left), к аргументу и возвращаемому значению типа функции f :: a -> b.

3.1  Отступление: функторы, механика за сценой

Стоит отметить, что тип функциональной стрелки l -> r в Haskell имеет два типовых параметра (l и r); эту стрелку допустимо записывать на уровне типов как (->) l r. Аналогично, скажем, двухпараметрический тип пары (a,b) можно записать как (,) a b. Допускается частичное применение конструктора типа на уровне типов — та стрелка (l ->), которую мы неформально «приписывали» выше, имеет в Haskell законное формальное определение: (->) l. Это уже однопараметрический тип: второй параметр типа связан типом l.

Интересно, что этот тип, как и многие библиотечные однопараметрические типы (тип списка, Maybe, IO) является функтором: в Control.Monad.Instances определено

то есть рассматриваемое нами сечение композиции есть не что иное, как fmap для нашей стрелки (l ->)! Это нетрудно понять, сравнив тип fmap для неё

с типом функции fmap, скажем, для списка,

или с общим определением

Заметим, что в теории категорий функтор (l ->) называют ковариантным hom-функтором [6].

3.2  Дважды левое сечение

Рассмотрим теперь, какие полезные конструкции можно извлечь из такой связи между функциональной стрелкой со связанным левым параметром и левым сечением композиции. Напомним: тип левого сечения (f . ) :: (l -> a) -> (l -> b) получается «приписыванием» стрелочки (l ->) слева к аргументу и возвращаемому значению типа функции f :: a -> b. Что будет, если осуществить эту операцию два раза подряд? Получающаяся конструкция имеет тип

Если абстрагироваться по f и убрать некоторые лишние скобки, получим

или, в более удобном для практических целей виде,

Для f :: a -> b и g :: l2 -> l1 -> a получаем типизацию (f . ) . g :: l2 -> l1 -> b. Соответствующая диаграмма имеет вид

Напомним, что функцию g мы изображаем на диаграммах обычными стрелками, результирующую конструкцию — стрелками из точек. В «точечном» стиле вызов конструкции (f . ) . g на аргументах x :: l2, y :: l1 эквивалентен вызову

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

Примеры.

Бесточечное определение takeWhile. Имеем библиотечную функцию

которая возвращает первый элемент пары, и библиотечную функцию

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

которая должна вернуть длиннейший префикс списка, все элементы которого удовлетворяют предикату, может быть определена в бесточечном стиле так:

Бесточечное определение mapM. Имеем библиотечные функции

Тогда библиотечная функция

может быть определена в бесточечном стиле так

Поиск без использования Maybe. Имеем библиотечные функции

Тогда функция с типом (Num a) => (a -> Bool) -> [a] -> a, возвращающая 0 при неудачном поиске в списке чисел и найденное число при удачном, может быть определена в бесточечном стиле так

3.3  Многократное левое сечение

Если применить операцию левого сечения композиции не два раза подряд, а три или четыре, мы получим возможность «прицеплять» функцию f, как обработчик результата функции трёх или четырёх аргументов. Для трёх применений имеем

Соответствующая диаграмма имеет вид

В «точечном» стиле вызов конструкции ((f . ) . ) . g на аргументах x :: l3, y :: l2, z :: l1 эквивалентен вызову

Приведем пример использования конструкции ((f . ) . ) . g. Выражение

работает как

только над результирующим списком [c] выполняется свертка умножением

Проверим в GHCi:

Действительно (1 + 3) * (2 + 2) * (3 + 1) = 64.

Для четырёх последовательных применений левого сечения композиции получаем

Диаграмма

В «точечном» стиле вызов конструкции (((f . ) . ) . ) . g на аргументах x :: l4, y :: l3, z :: l2, v :: l1 эквивалентен вызову

Ясно, что эта техника легко обобщается на случай произвольного числа аргументов у функции g.

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

4  Правое сечение композиции

Чтобы породить более богатое семейство бесточечных композиционных конструкций, полезно воспользоваться правым сечением композиции ( . f). Начнём, как обычно, с примеров:

Видно, что для произвольной функции

тип правого сечения композиции имеет вид

или, эквивалентно,

Можно сформулировать это так: сечение ( . f) преобразует переданную в качестве аргумента функцию g :: b -> r в функцию g' :: a -> r; это превращение происходит с помощью функции f :: a -> b:

В виде диаграммы:

Менее формально: тип правого сечения ( . f) :: (b -> r) -> (a -> r) получается «приписыванием» стрелочки (-> r) справа к аргументу и возвращаемому значению типа функции f :: a -> b и перестановкой аргументов (в отличие от левого сечения, где последовательность аргументов сохранялась).

4.1  Отступление: контрафункторы

Функциональная стрелка со связанным правым аргументом (-> r) не может быть напрямую формализована в Haskell. В библиотеке category-extras Эдварда Кметта [4] имеется определение

упаковывающее стрелку (l -> r) в двухпараметрический тип ContraF. Частичное применение этого типа ContraF r является полным эквивалентом стрелки со связанным правым аргументом (-> r).

Из-за перестановки аргументов тип правого сечения композиции не может являться функтором. В теории категорий, однако, для этого случая вводится понятие контравариантного функтора. В библиотеке category-extras контравариантный функтор реализован как класс типов

При этом для частичного применения типа ContraF r имеется объявление экземпляра³

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

5  Конструкции, порождаемые обоими сечениями

Теперь мы можем осуществлять и левое и правое сечение, при этом стрелки к типу будут подписываться слева и справа соответственно. Во втором случае следует также не забыть переставлять аргументы.

Например, если сначала применить правое сечение, а потом левое, получим

или

Если сначала применить левое сечение, а потом правое, получим

Два правых сечения дадут

Здесь a и b оказались на месте, потому что имела место двукратная перестановка: сначала a поменялось с b, затем (b -> r1) с (a -> r1).

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

5.1  Правое сечение, потом левое

Правое сечение композиции, а затем левое над его результатом (( . f) . ), порождают для f :: a -> b и g :: l2 -> b -> r1 конструкцию ( . f) . g :: l2 -> a -> r1:

Соответствующая диаграмма имеет вид

Напомним, что функцию g мы изображаем на диаграммах обычными стрелками, результирующую конструкцию — стрелками из точек. В «точечном» стиле вызов конструкции ( . f) . g на аргументах x :: l2, y :: a эквивалентен вызову

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

Примеры.

Бесточечное определение replicate. Имеем библиотечные функции

Тогда библиотечная функция

может быть определена в бесточечном стиле так

Отображение над хвостом списка. Имеем библиотечные функции

Тогда функция с типом (a -> b) -> [a] -> [b], осуществляющая отображение переданной функции на хвост переданного списка, может быть записана в бесточечном виде так

Увеличение элементов списка перед «зиповкой». Имеем библиотечные функции

Тогда функция с типом (Enum a) => (a -> b -> c) -> [a] -> [b] -> [c], осуществляющая однократное увеличение элементов первого списка, может быть записана в бесточечном виде так

Фильтрация элементов списка перед свёрткой. Имеем библиотечные функции

Тогда функция с типом (Num a, Ord a) => (a -> a -> a) -> [a] -> a, осуществляющая фильтрацию элементов списка по условию (> 3) перед его свёрткой, может быть записана в бесточечном виде так:

5.2  Сначала правое сечение, а потом левые

Если применить операцию правого сечения композиции, а затем выполнить над его результатом несколько левых, мы получим возможность «вставлять» функцию f, как предварительный обработчик последнего аргумента функции нескольких переменных. Для трёх сечений получаем

Соответствующая диаграмма имеет вид

В «точечном» стиле вызов конструкции (( . f) . ) . g на аргументах x :: l3, y :: l2, z :: a эквивалентен вызову

Приведем пример использования конструкции (( . f) . ) . g. Выражение

это тот же foldr, только над однократно увеличенными элементами списка. Действие map succ посредством обсуждаемой конструкции перенаправляется на последний (третий) аргумент функции

то есть на список. Проверим в GHCi:

Действительно 2 * 3 * 4 = 24.

Для четырёх сечений (правое, левое, левое, левое) получаем

Диаграмма

«Точечный» эквивалент конструкции ((( . f) . ) . ) . g на аргументах x :: l4, y :: l3, z :: l2, v :: a таков

Эта техника легко обобщается на случай произвольного числа аргументов у функции g.

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

5.3  Сначала левое сечение, а потом правое

Левое сечение композиции, а затем правое над его результатом ( . (f . )), порождают для f :: a -> b и g :: (l1 -> b) -> r2 конструкцию g . (f . ) :: (l1 -> a) -> r2:

Соответствующая диаграмма имеет вид

Напомним, что функцию g мы изображаем на диаграммах обычными стрелками, результирующую конструкцию — стрелками из точек. В «точечном» стиле вызов конструкции g . (f . ) на аргументе h :: l1 -> a эквивалентен вызову

Итак, конструкция g . (f . ) порождает функцию, представляющую собой функцию функционального аргумента, и осуществляющую вызов g на композиции функции f и этого функционального аргумента.

Пример.

Имеем библиотечные функции

Последняя определена только для символов '0'..'9', 'a'..'f', 'A'..'F'. Тогда конструкция

работает как отображение map, только над каждым элементом списка после⁴ вызова функции типа a -> Char, передаваемой в это выражение в качестве функционального аргумента, выполняется ещё вызов digitToInt.

Проверка в сессии GHCi даёт

Вызов функции succ, передаваемой как аргумент конструкции, происходит до вызова функции digitToInt, встроенной в конструкцию (фактически в map передаётся композиция digitToInt . succ). Поэтому во втором тестировании и выбрасывается исключение: succ 'F' = 'G', а на значении 'G' функция digitToInt не определена.

5.4  Дважды правое сечение

Правое сечение композиции, повторённое два раза ( . ( . f)), порождает для f :: a -> b и g :: (a -> r1) -> r2 конструкцию g . ( . f) :: (b -> r1) -> r2:

Соответствующая диаграмма имеет вид

Напомним, что функцию g мы изображаем на диаграммах обычными стрелками, результирующую конструкцию — стрелками из точек. В «точечном» стиле вызов конструкции g . ( . f) на аргументе h :: b -> r1 эквивалентен вызову

Итак, конструкция g . ( . f) порождает функцию, представляющую собой функцию функционального аргумента, и осуществляющую вызов g на композиции этого функционального аргумента и функции f.

Пример:

Рассмотрим конструкцию, очень похожую на конструкцию из предыдущего примера:

Она работает как отображение map, только над каждым элементом списка помимо вызова функции типа Int -> c, передаваемой в это выражение в качестве функционального аргумента, выполняется ещё предварительный вызов digitToInt.

Проверка в сессии GHCi даёт

Вызов функции succ, передаваемой как аргумент конструкции, происходит после вызова функции digitToInt, встроенной в конструкцию (фактически в map передаётся композиция succ . digitToInt). Поэтому в отличие от прошлого примера во втором тестировании исключения на символе 'F' не происходит: digitToInt 'F' = 15 и succ 15 = 16.

6  Дополнительные техники

Если взглянуть на разобранные выше цепочки сечений, может показаться, что многие полезные конструкции остались вне нашего рассмотрения. Из диаграмм видно, что функция-обработчик f, модифицирующая функцию нескольких аргументов g, может подключаться либо как постобработчик результата g, либо как «предварительный» обработчик последнего из аргументов g. А как действовать в случае, если требуется организовать предобработчик другого (не последнего) аргумента g?

Оказывается, здесь нам помогает тот факт, что все функции в Haskell могут рассматриваться как функции одного аргумента. Предположим, нас интересует бесточечное представление для конструкции

Её тип

и диаграмма

Легко увидеть, что в этой конструкции функция g может трактоваться как функция одного аргумента (типа b): g :: b -> (c -> d), то есть тип конструкции сводится к типу простой композиции

где введено обозначение t = (c -> d). То есть конструкция может быть в бесточечном стиле записана как

несмотря на то, что функция g является функцией двух аргументов. Этот подход работает и в других аналогичных случаях; важно лишь осознавать, что любой аргумент функции может рассматриваться как последний.

Здесь можно вспомнить пример, приведенный в начале статьи — функцию

Функция одного аргумента ( * 60) применяется к первому аргументу функции двух аргументов (+). Отсюда сразу получается бесточечное определение

которое раньше выводилось как результат долгих преобразований.

Коротко коснёмся композиции сечений композиции. Независимо от того, используются правые сечения или левые, такая конструкция описывает композицию трёх функций

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

Композиция правых сечений избавляет от первого аргумента

Композиция левого и правого (или правого и левого) сечения позволяет избавиться от среднего аргумента

Более сложные конструкции из операторов композиций также могут быть предметом рассмотрения. Более подробно с этой темой можно ознакомиться в [3, 7]. Например, в [7] демонстрируется, как по конструкции

эффективно получить ее полный бесточечный эквивалент

7  Заключение

Мы выяснили, что сечения оператора композиции являются полезными инструментами для построения широкого спектра бесточечных выражений. Сформулируем основные практические выводы.

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

• Эта конструкция применима к функции g того количества аргументов, сколько сечений использовалось.
• Функция f работает в этой конструкции как постобработчик результата функции нескольких переменных g.

Для случаев, когда g является функцией одного, двух, трех и четырех аргументов, имеем, соответственно, эквивалентности (в «точечной» форме):

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

• Эта конструкция применима к функции g того количества аргументов, сколько сечений использовалось.
• Функция f работает в этой конструкции как предварительный обработчик последнего аргумента функции нескольких переменных g.

Если же нам требуется организовать предварительный обработчик любого другого (не последнего) аргумента функции нескольких переменных, мы делаем этот аргумент последним искусственно, рассматривая всё, что идёт после этого аргумента, как возвращаемое (функциональное) значение. Для случая, когда g является функцией двух аргументов, «точечные» эквивалентности для всевозможных вариантов «подключения» предобработчика f таковы:

Для случая, когда g является функцией трех аргументов:

Для случая, когда g является функцией четырех аргументов:

В заключение хотелось бы ещё раз подчеркнуть, что бесточечный стиль — всего лишь одна из техник программирования на Haskell. Разумный программист понимает, что никакой техникой не стоит злоупотреблять в ущерб другим. Компактность, возникающая благодаря использованию этого стиля, имеет свою цену: глядя на бесточечную конструкцию иногда трудно восстановить количество и тип необходимых аргументов. Поэтому разобранные в статье конструкции можно порекомендовать использовать в ситуациях, когда их компонентами являются широко известные библиотечные функции из семейств fmap, fold, scan, zipWith и им подобных.

Список литературы

[1]

J. Backus. Can programming be liberated from the von neumann style? Communications of the ACM, 21(8):613–641, 1978.

[2]

Jeremy Gibbons. A pointless derivation of radixsort. Journal of Functional Programming, 9(3):339–346, 1999.

[3]

Haskell Wiki. Pointfree. http://www.haskell.org/haskellwiki/Pointfree.

[4]

Edward Kmett. Various modules and constructs inspired by category theory. http://comonad.com/haskell/category-extras/dist/doc/html/category-extras/index.html.

[5]

Кирпичёв Е. Элементы функциональных языков. Практика функционального программирования, №3, декабрь 2009.

[6]

Маклейн С. Категории для работающего математика. ФизМатЛит, 2004.

[7]

Москвин Д. Функциональные типы и композиция функций в Хаскелле. RSDN Magazine, №3, 2007.

1

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

2

Для того, чтобы подчеркнуть интересующие нас свойства, имена типовых переменных здесь несколько изменены по сравнению со стандартным выводом GHCi. В определенной позиции используется имя типа l от слова left (левый), причины этого станут ясны ниже.

3

В теории категорий функтор (-> r) называют контравариантным hom-функтором [6].

4

Термины «после» и «до» здесь используются для маркирования последовательности аппликаций; мы говорим что в вызове f (g x) функция f применяется после g, невзирая на возможные тонкости операционной семантики.

Этот документ был получен из L^AT_EX при помощи H^EV^EA

© 2009—2011  «Практика функционального программирования»ISSN 2075-8456