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

Question

Я работаю через 20 Intermediate Haskell Exercises на данный момент, что довольно весело. Он включает в себя реализацию различных экземпляров типов 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-х кортежах. На основе этого подхода используют Conal Elliott's Semantic Editor Combinators.

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

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

Важно, если вы хотите использовать любое из этого в реальном коде, нужно подумать о том, что означает выражение и как это отражено в структуре. Если вы это сделаете, а затем переконфигурируйте его в беспутный стиль с использованием значимых комбинаторов, вы часто делаете намерение кода clearer, чем в противном случае, в отличие от типичного вывода 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

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

Answer 4

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

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

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

Вот banana2:

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 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) 

и т.д.