Вложенное функциональное приложение

Легко определить такой оператор, как

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

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

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

Либо одинаково тривиально определить. Самое приятное в том, что теперь вы можете сделать что-то вроде

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

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

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

Ответы

Ответ 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)

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

Ответ 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 для дальнейшего вдохновения.

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