Какова общая схема записи функции в бесточечном стиле?

Как продемонстрировала утилита pointfree, любое такое преобразование можно выполнить автоматически. Однако результат чаще запутывается, чем улучшается. Если цель состоит в том, чтобы повысить удобочитаемость, а не разрушить ее, то первой целью должно быть определение почему выражение имеет определенную структуру, поиск подходящей абстракции и построение таким образом.

Простейшая структура — это просто объединение элементов в линейный конвейер, который представляет собой простую композицию функций. Это само по себе достаточно далеко заводит нас, но, как вы заметили, оно не справляется со всем.

Одним из обобщений являются функции с дополнительными аргументами, которые можно наращивать постепенно. Вот один пример: Определите onResult = (. (.)). Теперь, применяя onResult n раз к начальному значению id, вы получаете композицию функций с результатом n-арной функции. Итак, мы можем определить comp2 = onResult (.), а затем написать comp2 not (&&), чтобы определить операцию И-НЕ.

Еще одно обобщение, которое на самом деле охватывает вышеизложенное, заключается в определении операторов, применяющих функцию к компоненту большего значения. Примером здесь могут быть first и second в Control.Arrow, которые работают с двумя кортежами. На этом подходе основаны комбинаторы семантического редактора Конала Эллиотта.

Немного другой случай, когда у вас есть функция с несколькими аргументами для некоторого типа b и функция a -> b, и вам нужно объединить их в функцию с несколькими аргументами, используя a. Для общего случая двумерных функций модуль Data.Function предоставляет комбинатор on, который можно использовать для написания выражений типа compare `on` fst для сравнения двухкортежей по их первым элементам.

Это более сложная проблема, когда один аргумент используется более одного раза, но здесь есть значимые повторяющиеся шаблоны, которые также можно извлечь. Распространенным случаем здесь является применение нескольких функций к одному аргументу, а затем сбор результатов с помощью другой функции. Это соответствует экземпляру Applicative для функций, что позволяет нам писать выражения вроде (&&) <$> (> 3) <*> (< 9) для проверки того, попадает ли число в заданный диапазон.

Если вы хотите использовать что-либо из этого в реальном коде, важно подумать о том, что выражение означает и как это отражается в структуре. Если вы сделаете это, а затем преобразуете его в бесточечный стиль, используя осмысленные комбинаторы, вы часто сделаете цель кода более ясной, чем она была бы в противном случае, в отличие от типичного вывода pointfree.

Да! Один из приемов — писать точки в префиксной записи, а не в инфиксной. Тогда вы сможете найти новые вещи, похожие на композицию функций. Вот пример:

banana2 f = appleTurnover . banana1 f
          = (.) appleTurnover (banana1 f)
          = ((.) appleTurnOver) . banana1 $ f
banana2 = (appleTurnover .) . banana1

Исходный код утилиты pointfree содержит больше, но этот обрабатывает множество случаев.

banana4 f x y = appleTurnover . banana3 f x y
              = (.) appleTurnover ((banana3 f x) y)
              = ((.) appleTurnover) . (banana3 f x) $ y
banana4 f x = ((.) appleTurnover) . (banana3 f x)
            = (.) ((.) appleTurnover) (banana3 f x)
            = ((.) ((.) appleTurnover)) ((banana3 f) x)
            = ((.) ((.) appleTurnover)) . (banana3 f) $ x
banana4 f = ((.) ((.) appleTurnover)) . (banana3 f)
          = (.) ((.) ((.) appleTurnover)) (banana3 f)
          = ((.) ((.) ((.) appleTurnover))) (banana3 f)
          = ((.) ((.) ((.) appleTurnover))) . banana3 $ f
banana4 = ((.) ((.) ((.) appleTurnover))) . banana3
        = (((appleTurnover .) .) .) . banana3

Я использую следующий термин система перезаписи:

\x -> f x ------> f 
f y x ----------> flip f x y
\x -> f (g x) --> f . g

Оно неполное (почему читайте в книгах по комбинаторной логике), но достаточно:

Вот банан2:

banana2 f = appleTurnover . banana1 f

Перепишите как лямбда:

banana2 = \f -> appleTurnover . banana1 f

Напишите (.) в префиксном стиле:

banana2 = \f -> (.) appleTurnover (banana1 f)

Обратите внимание, что

banana2 = \f -> ((.) appleTurnover) (banana1 f)

Таким образом, правило 3 может быть применено. f это (.) appleTurnover, а g это banana:

banana2 = ((.) appleTurnover) . banana1

Существует пакет pointfree, который берет определение функции Haskell и пытается переписать его в стиле pointfree. Я бы посоветовал поэкспериментировать с ним, чтобы получить новые идеи. Подробнее см. на этой странице; пакет доступен здесь.

Поскольку бесточечный стиль — это стиль комбинаторов, просто примените определения известных комбинаторов, прочитав их задом наперед, чтобы произвести замену:

B f g x = f (g x)     -- (.) , <$> for ((->) a)
C f x y = f y x       -- flip
K x y = x             -- const
I x = x               -- id
S f g x = f x (g x)   -- <*> , ap  for ((->) a)
W f x = f x x         -- join
(f >>= g) x = g (f x) x
(f =<< g) x = f (g x) x

Иногда liftMx, liftAx, sequence, sequenceA могут все упростить. Я бы также рассматривал foldr, unfoldr, iterate, until и т. д. в качестве базовых комбинаторов.

Часто также помогает использование разделов оператора:

op a b = (a `op` b) = (`op` b) a = (a `op`) b

Некоторые паттерны могут стать привычными и поэтому использоваться напрямую:

((f .) . g) x y = f (g x y)
((. f) . g) x y = g x (f y)

(((f .) .) . g) x y z = (f .) (g x y) z = f (g x y z)
(((. f) .) . g) x y z = (. f) (g x y) z = g x y (f z)

и т.п.