Функциональные комбинаторы в Clojure

В процессе написания на Clojure своего маленького, но полезного софта, а также благодаря титаническим усилиям авторов журнала «Практика функционального программирования» (особенно, 3-го выпуска) на поприще лечения функционально-шоковой терапией (шоковой по причине хаскеля, вестимо) оопнуто-императивного мозга ко мне пришло понимание особой полезности и удобства применения функций-комбинаторов других функций.

Пускай это звучит заумно, но объяснение на пальцах полностью раскрывает суть этой простой вещи. Представим, есть у нас две функции-предиката, которые возвращают только истину или ложь — предикаты «жив?», alive? и «мёртв?», dead?. Нам нужно из этих предикатов составить третий предикат, проверяющий сложное условие, например — «не-жив-не-мёртв?», nor-dead-nor-alive? (не факт, что этот предикат всегда будет возвращать false, учитывая динамичность Clojure и особенности применения, но тем не менее). Берем эти предикаты и конструируем эту функцию так, как мы обычно это делаем

(defn nor-dead-nor-alive? [x] 
  (and (not dead? x) (not alive? x)))

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

(def nor-dead-nor-alive? (fn/and (fn/not dead?) (fn/not alive?)))

Может это и не лучший пример для комбинаторов, в плане небольшого шума, который добавляют префиксы fn/, да и проблем с документацией добавит, но он достаточно прост, чтобы показать саму концепцию. В большинстве случаев использование комбинаторов позволит избавиться от приличного объема копипасты, что приведет к более понятному коду с ясно выраженной сутью вычисления.

Практичный пример.

Прошлый пример с функциями «жив?» и «мёртв?» был довольно игрушечным, на этот раз приведу пример из маленькой полезной программы, которую я написал для себя. Это качалка с местного файлообменника, внутри которой пачка асинхронных агентов делает своё нелёгкое сетевое дело. Агенты организованы в окружение, они могут быть живыми — предикат alive?, иметь некий таг — ацессор tag, и принадлежать к некоторому типу агентов — ацессор type. Мне нужна была функция для выбора «следующего живого агента того же типа, но без тага». Вот реализация с комбинатором:

(defn next-alive-untagged-after [ag]
  (next-after-when (fn/and alive? 
                           (fn/not tag)
                           (partial same type ag))
                   (self ag) (env ag)))

и без комбинатора

(defn next-alive-untagged-after [ag]
  (next-after-when (fn [x] (and (alive? x) 
                                (not (tag x)) 
                                (same type ag x)))
                   (self ag) (env ag)))

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

Реализация комбинаторов.

Комбинаторов много хороших и разных, но в статье и большей части своего кода я использовал только три наиболее полезных «логических» комбинатора — fn/and, fn/or и fn/not. Оригинальный код этих комбинаторов я вычитал в замечательной книге Пола Грэма «On Lisp» (там еще много подобных плюшек). Реализация их на Clojure чуть более функциональна и проще для понимания благодаря деструктуризации аргументов функций и тому, что это Lisp-1 (не нужен funcall).

Нижеследующий код определяет пространство имен fn, чтобы использовать этот модуль в своих программах укажите в зависимостях leiningen

[fn "1.0.0"]

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

(ns fn
  (:refer-clojure :exclude [not and or]))

Этот код определяет пространство имён fn. В Clojure это имя зарезервировано под фундаментальный макрос, конструктор функций, но это не создаст проблем при использовании. Другое дело, что без префикса fn/ комбинаторами невозможно будет воспользоваться в обычном коде, однако, пораскинув мыслью, всё становится на свои места — хорошие имена разлетаются как горячие пирожки, на всех не напасёшься, префикс же подчёркивает функциональный аспект при употреблении этих конструкций. :refer-clojure :exclude исключает импорт имён and, or и not из пространства имён ядра языка clojure.core. Задействовать эту маленькую библиотеку в своей программе можно лишь с помощью require; use работать не будет из-за перекрытия имен.

Заранее определим имена функций в нашем модуле

(declare not and or)

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

Комбинатор fn/not это старый добрый complement, для удобстава возвращающий «пересечение» комплементарных функций, если его вызвать с несколькими аргументами

(fn/not f) => (complement f)
(fn/not f g h ...) => (and (fn/not f) (fn/not g) (fn/not h) ...)

(defn not
  ([f] (complement f))
  ([f & fs] (and (not f)
                 (apply and (map not fs)))))

Комбинатор fn/and возвращает «пересечение» функций — функцию, которая возвращает что-либо (non-nil), только если все пересекаемые функции возвращают что-либо:

(and f g h ...) => (fn [xs] (and (f xs) (g xs) (h xs) ...))

(defn and
  ([f] f)
  ([f & fs] (let [chain (apply and fs)]
              (fn [& xs] (clojure.core/and (apply f xs)
                                           (apply chain xs))))))

Комбинатор fn/or возвращает «объединение» функций — функцию, которая возвращает что-либо, когда хотя бы одна функция из объединяемых возвращает что-либо:

(or f g h ...) => (fn [xs] (or (f xs) (g xs) (h xs) ...))

(defn or
  ([f] f)
  ([f & fs] (let [chain (apply or fs)]
               (fn [& xs] (clojure.core/or (apply f xs)
                                           (apply chain xs))))))