Приложение с вложенными функциями

Question

Довольно просто определить оператор как

(@) :: [x -> y] -> [x] -> [y]

, который принимает список функций и список входов и возвращает список выходов. Есть два очевидных способа реализовать это:

1. Применить первую функцию к первому входу, вторую функцию ко второму входу и т. Д.
2. Применить каждую функцию к каждому входу.

Любой из них одинаково тривиален для определения. Приятно то, что теперь вы можете делать что-то вроде

foo :: X -> Y -> Z -> R

bar :: [X] -> [Y] -> [Z] -> [R]
bar xs ys zs = [foo] @@ xs @@ ys @@ zs

Это обобщает произвольное число аргументов функции.

---

Пока все хорошо. Теперь о проблеме: как изменить сигнатуру типа для @@ так, чтобы сигнатура типа для bar стала

bar :: [X] -> [Y] -> [Z] -> [[[R]]]

Нетрудно реализовать функцию с этим типом; любой из них сделает это:

bar xs ys zs = map (\ x -> map (\ y -> map (\ z -> foo x y z) zs) ys) zs
bar xs ys zs = map (\ z -> map (\ y -> map (\ x -> foo x y z) xs) ys) zs

Я не привередлив относительно того, какой результат я получу. Но я не могу понять, как настроить оператор @@, чтобы сделать это.

---

Очевидная вещь, которую стоит попробовать

(@@) :: [x -> y] -> [x] -> [[y]]

Это не сложно реализовать, но это вам не поможет. Теперь у вас есть

[foo] @@ xs :: [[Y -> Z -> R]]

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

Я пробовал несколько других возможных типов подписей, но ни одна из них не приближает меня к ответу. Может кто-нибудь либо дать мне решение, либо объяснить, почему его не существует?

Answer 1

Вы уже поняли, почему это так хлопотно.Ваша функция (@@) применяется к входам различных типов (например, [x->y], [[x -> y]] и т. Д.). Это означает, что ваша сигнатура типа для @@ является слишком строгой ; вам необходимо добавить некоторыеполиморфизм, чтобы сделать его более общим, чтобы использовать его с вложенными списками. Так как Haskell реализует полиморфизм с классами типов, это хорошее направление, чтобы попробовать.

Как это происходит, с этой проблемой, если вы знаете тип LHSВы можете однозначно определить как RHS, так и результат. Когда вход имеет тип [a->b], RHS должен быть [a], а результат должен быть [[b]]. Это можно упростить до ввода a->b, RHS[a], и результат [b]. Поскольку LHS определяет другие параметры и результат, мы можем использовать fundeps или семейства типов для представления других типов.

{-# LANGUAGE TypeFamilies, UndecidableInstances #-}

class Apply inp where
  type Left inp    :: *
  type Result  inp :: *
  (@@) :: inp -> [Left inp] -> [Result inp]

Теперь, когда у нас естьТип класса, мы можем сделать очевидный экземпляр для функции:

instance Apply (a -> b) where
  type Left (a -> b)   = a
  type Result (a -> b) = b
  (@@) = map

Экземпляр списка тоже не так уж плох:

instance Apply f => Apply [f] where
  type Left [f]   = Left f
  type Result [f] = [Result f]
  l @@ r = map (\f -> f @@ r) l
  -- or    map (@@ r) l

Теперь наш метод класса @@ долженork с произвольно глубокими списками.Вот несколько тестов:

*Main> (+) @@ [1..3] @@ [10..13]
[[11,12,13,14],[12,13,14,15],[13,14,15,16]]'s

let foo :: Int -> Char -> Char -> String
    foo a b c = b:c:show a

*Main> foo @@ [1,2] @@ "ab" @@ "de"
[[["ad1","ae1"],["bd1","be1"]],[["ad2","ae2"],["bd2","be2"]]]

Возможно, вы захотите взглянуть на реализацию printf для дальнейшего вдохновения.

Редактировать: Вскоре после публикации я понял, что можно обобщить контейнервведите мой Apply класс от List до Applicative, затем используйте аппликативный экземпляр вместо map.Это позволило бы использовать как обычный список, так и поведение ZipList.

Answer 2

На самом деле, это вообще не требует классов типов! Вы теряете немного удобства, избегая классов типов, но это все.

Ключевым моментом является то, что, несмотря на повторное использование одного комбинатора, полиморфизм позволяет различать тип каждого использования. Это тот же принцип, что и для выражений в стиле Applicative, таких как f <$> xs <*> ys <*> zs, и конечный результат здесь будет выглядеть аналогично. Таким образом, мы сделаем это для любых Functor, а не только для списков.

Разница между этой и Applicative версией заключается в том, что мы углубляемся во вложенные Functor с каждым шагом. Необходимый полиморфизм требует гибкости на самом внутреннем слое, поэтому для этого мы воспользуемся приемом продолжения, где результатом каждого комбинатора является функция, которая принимает преобразование для использования на самом внутреннем слое.

Нам понадобятся два оператора: один, который запускает цепочку, и один, который продолжает ее постепенно. Начиная с последнего:

(@@) :: (Functor f) => (((a -> b) -> f c) -> r) -> f a -> (b -> c) -> r
q  @@ xs = \k -> q (\f -> k . f <$> xs)

Это принимает новый аргумент справа, а выражение в процессе слева. Результат принимает функцию k, которая указывает, что нужно сделать, чтобы получить окончательный результат. k объединяется с любым уже имеющимся выражением, и оба сопоставляются с новым аргументом. Это запутанно, но должно показаться знакомым всем, кто разбирает код в стиле CPS.

(<@) :: (Functor f, Functor g) => f (a -> b) -> g a -> (b -> c) -> f (g c)
fs <@ xs = (<$> fs) @@ xs

Цепочка начинается с простого сопоставления всего остального с первым аргументом.

В отличие от более простого случая Applicative, нам также необходимо явно завершить цепочку. Как и в случае монады Cont, самый простой способ сделать это - применить результат к функции тождества. Мы дадим это полезное имя:

nested = ($ id)

Теперь мы можем делать такие вещи:

test2 :: [X -> Y -> R] -> [X] -> [Y] -> [[[R]]]
test2 fs xs ys = nested (fs <@ xs @@ ys)

test3 :: [X -> Y -> Z -> R] -> [X] -> [Y] -> [Z] -> [[[[R]]]]
test3 fs xs ys zs = nested (fs <@ xs @@ ys @@ zs)

Не совсем так, как версия класса типов, но она работает.