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

Question

Я сейчас выполняю 20 промежуточных упражнений на Хаскелле , что довольно забавное упражнение. Он включает в себя реализацию различных экземпляров классов типов Functor и Monad (и функций, которые принимают Functor s и Monad s в качестве аргументов), но с симпатичными именами, такими как Furry и Misty, чтобы скрыть то, что мы делать (делает для некоторого интересного кода).

Я пытался сделать это в стиле без точек, и мне было интересно, есть ли общая схема для превращения точечного (?) Определения в определение без точек. Например, вот класс типов для Misty:

class Misty m where
  unicorn :: a -> m a
  banana :: (a -> m b) -> m a -> m b

(функции unicorn и banana являются return и >>=, если это не очевидно), и вот моя реализация apple (эквивалентная flip ap):

apple :: (Misty m) => m a -> m (a -> b) -> m b
apple x f = banana (\g -> banana (unicorn . g) x) f

В последующих частях упражнений вы реализуете версии liftM, liftM2 и т. Д. Вот мои решения:

appleTurnover :: (Misty m) => m (a -> b) -> m a -> m b
appleTurnover = flip apple

banana1 :: (Misty m) => (a -> b) -> m a -> m b
banana1 =  appleTurnover . unicorn

banana2 :: (Misty m) => (a -> b -> c) -> m a -> m b -> m c
banana2 f = appleTurnover . banana1 f

banana3 :: (Misty m) => (a -> b -> c -> d) -> m a -> m b -> m c -> m d
banana3 f x = appleTurnover . banana2 f x

banana4 :: (Misty m) => (a -> b -> c -> d -> e) -> m a -> m b -> m c -> m d -> m e
banana4 f x y = appleTurnover . banana3 f x y

Теперь banana1 (эквивалент liftM или fmap) мне удалось реализовать в стиле pointfree, подходящим определением appleTurnover. Но с другими тремя функциями мне пришлось использовать параметры.

Мой вопрос: существует ли рецепт для превращения подобных определений в определения без точек ?

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

Answer 3

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

\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

Answer 4

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

Answer 5

Поскольку стиль 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)

и т. д.