Уплотненное применение функции

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

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

Ключевым моментом является то, что, несмотря на повторное использование одного комбинатора, полиморфизм позволяет различать каждый тип использования. Это тот же самый принцип, что и у 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) 

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

Answer 2

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

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

{-# 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 

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

*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 реализации для дальнейшего вдохновения.

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