Оператор композиции функции Хаскелла типа (c → d) → (a → b → c) → (a → b → d)

Question

Композиция обычной функции имеет тип

(.) :: (b -> c) -> (a -> b) -> a -> c

Я полагаю, это следует обобщить для таких типов, как:

(.) :: (c -> d) -> (a -> b -> c) -> a -> b -> d

Конкретный пример: вычисление квадрата разности.Мы могли бы написать diffsq a b = (a - b) ^ 2, но мне кажется, что Я мог бы написать (-) и (^2), чтобы написать что-то вроде diffsq = (^2) . (-).

Я не могу,конечно.Единственное, что я могу сделать, это использовать кортеж вместо двух аргументов для (-), преобразовав его в uncurry, но это не то же самое.

Возможно лиделать то, что я хочу?Если нет, то что я неправильно понимаю, что заставляет меня думать, что это возможно?

---

Примечание: Это уже было задано здесь , но ответ(что я подозреваю, должен существовать) не было дано.

Answer 1

Моя предпочтительная реализация для этого

fmap . fmap :: (Functor f, Functor f1) => (a -> b) -> f (f1 a) -> f (f1 b)

Хотя бы потому, что это довольно легко запомнить.

При создании экземпляров f и f1 для (->) c и (->) d соответственно вы получаете тип

(a -> b) -> (c -> d -> a) -> c -> d -> b

это тип

(.) . (.) ::  (b -> c) -> (a -> a1 -> b) -> a -> a1 -> c

но немного проще отказаться от версии fmap . fmap и она обобщает на другие функторы.

Иногда это пишется fmap fmap fmap, но записывается как fmap . fmap, его можно легко расширить, чтобы разрешить больше аргументов.

fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h) => (a -> b) -> f (g (h a)) -> f (g (h b))

fmap . fmap . fmap . fmap 
:: (Functor f, Functor g, Functor h, Functor i) => (a -> b) -> f (g (h (i a))) -> f (g (h (i b))

* * Тысяча двадцать-одина и т.д.

В общем случае fmap, составленный сам с собой n раз, может использоваться для fmap n уровней глубины!

И поскольку функции образуют Functor, это обеспечивает верстку для n аргументов.

Для получения дополнительной информации см. Conal Elliott Semantic Editor Combinators .

Answer 2

Недоразумение заключается в том, что вы думаете о функции типа a -> b -> c как о функции двух аргументов с типом возврата c, тогда как на самом деле это функция одного аргумента с типом возврата b -> c, поскольку тип функции ассоциируется справа (т.е. это то же самое, что и a -> (b -> c). Это делает невозможным использование стандартного оператора композиции функций.

Чтобы понять почему, попробуйте применить оператор (.) типа (y -> z) -> (x -> y) -> (x -> z) к двум функциям g :: c -> d и f :: a -> (b -> c). Это означает, что мы должны объединить y с c, а также с b -> c. Это не имеет особого смысла. Как y может быть одновременно c и функцией, возвращающей c? Это должно быть бесконечного типа. Так что это не работает.

То, что мы не можем использовать стандартный оператор композиции, не мешает нам определять наш собственный.

 compose2 :: (c -> d) -> (a -> b -> c) -> a -> b -> d
 compose2 g f x y = g (f x y)

 diffsq = (^2) `compose2` (-)

Обычно в этом случае лучше избегать использования стиля без очков и просто использовать

 diffsq a b = (a-b)^2

Answer 3

Я не знаю стандартной библиотечной функции, которая делает это, но шаблон без точек, который ее выполняет, состоит в составлении функции композиции:

Answer 4

Я собирался написать это в комментарии, но он немного длинный, и он опирается как на mightybyte, так и на hammar.

Я предлагаю стандартизировать операторы, такие как .* для compose2 и.** для compose3.Используя определение mightybyte:

(.*) :: (c -> d) -> (a -> b -> c) -> (a -> b -> d)
(.*) = (.) . (.)

(.**) :: (d -> e) -> (a -> b -> c -> d) -> (a -> b -> c -> e)
(.**) = (.) . (.*)

diffsq :: (Num a) => a -> a -> a
diffsq = (^2) .* (-)

modminus :: (Integral a) => a -> a -> a -> a
modminus n = (`mod` n) .* (-)

diffsqmod :: (Integral a) => a -> a -> a -> a
diffsqmod = (^2) .** modminus

Да, modminus и diffsqmod - очень случайные и бесполезные функции, но они были быстрыми и показывают смысл.Обратите внимание на то, как легко определить следующий уровень путем компоновки в другой функции компоновки (аналогично цепочке fmap, упомянутой Эдвардом).

(.***) = (.) . (.**)

На практике, начиная с compose12 и вышекороче написать имя функции, а не оператор

f .*********** g
f `compose12` g

Хотя подсчет звездочек утомителен, поэтому мы можем захотеть остановить соглашение на 4 или 5.

---

[править] Еще одна случайная идея: мы можем использовать .: для compose2, .:. для compose3, .:: для compose4, .::. для compose5, .::: для compose6, позволяя визуально определить количество точек (после начальной)отметьте, сколько аргументов для детализации.Я думаю, что мне больше нравятся звезды.

Answer 5

Как Макс указано в комментарии :

diffsq = ((^ 2) .) . (-)

Вы можете думать о f . g как о применении одного аргумента к g, а затем о передаче результата в f. (f .) . g применяет два аргумента к g, а затем передает результат в f. ((f .) .) . g применяет три аргумента к g и т. Д.

\f g -> (f .) . g :: (c -> d) -> (a -> b -> c) -> a -> b -> d

Если мы оставили разделительный оператор композиции с некоторой функцией f :: c -> d (частичное применение с f слева), мы получим:

(f .) :: (b -> c) -> b -> d

Итак, у нас есть эта новая функция, которая ожидает функцию от b -> c, но наш g равен a -> b -> c, или, что эквивалентно, a -> (b -> c). Нам нужно подать a, прежде чем мы сможем получить то, что нам нужно. Что ж, давайте повторим еще раз:

((f .) .) :: (a -> b -> c) -> a -> b -> d

Answer 6

Вот то, что я считаю элегантным способом достижения того, чего вы хотите.Класс типа Functor дает возможность «протолкнуть» функцию в контейнер, чтобы вы могли применить ее к каждому элементу, используя fmap.Вы можете думать о функции a -> b как о контейнере b s, каждый элемент которого проиндексирован элементом a.Поэтому естественно создать этот экземпляр:

instance Functor ((->) a) where
  fmap f g = f . g

(я думаю, что вы можете получить это, import выбрав подходящую библиотеку, но я не могу вспомнить какую.)

Теперь обычныйсостав f с g тривиально равен fmap:

o1 :: (c -> d) -> (b -> c) -> (b -> d)
f `o1` g = fmap f g

Функция типа a -> b -> c представляет собой контейнер контейнеров элементов типа c.Поэтому нам просто нужно дважды нажать нашу функцию f.Вот, пожалуйста:

o2 :: (c -> d) -> (a -> (b -> c)) -> a -> (b -> d)
f `o2` g = fmap (fmap f) g

На практике вы можете обнаружить, что вам не нужны o1 или o2, просто fmap.И если вы можете найти библиотеку, местоположение которой я забыл, вы можете обнаружить, что можете просто использовать fmap без написания дополнительного кода.