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

Question

Сейчас я прорабатываю 20 промежуточных упражнений на Хаскелле, и это довольно забавное упражнение. Это включает в себя реализацию различных экземпляров классов типов Functor а также Monad (и функции, которые занимают Functorс и Monadв качестве аргументов) но с милыми именами вроде 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 п раз к первоначальному значению id дает вам композицию функций с результатом n-арной функции. Таким образом, мы можем определить comp2 = onResult (.), а затем написать comp2 not (&&) определить операцию NAND.

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

Немного другой случай, когда у вас есть функция с несколькими аргументами для некоторого типа 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

E сть 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)

и т.п.