Изучай Haskell во имя добра!

При использовании обычных функторов мы можем просто отображать одно значение функтора с помощью функций. При использовании аппликативных функторов мы можем применять функцию между несколькими значениями функторов. Интересно также рассматривать тип этой функции в виде (a –> b –> c) –> (f a –> f b –> f c). Когда мы его воспринимаем подобным образом, мы можем сказать, что функция liftA2 берёт обычную бинарную функцию и преобразует её в функцию, которая работает с двумя аппликативными значениями.

Есть интересная концепция: мы можем взять два аппликативных значения и свести их в одно, которое содержит в себе результаты этих двух аппликативных значений в списке. Например, у нас есть значения Just 3 и Just 4. Предположим, что второй функтор содержит одноэлементный список, так как этого очень легко достичь:

ghci> fmap (\x –> [x]) (Just 4)

Just [4]

Хорошо, скажем, у нас есть значения Just 3 и Just [4]. Как нам получить Just [3,4]? Это просто!

ghci> liftA2 (:) (Just 3) (Just [4])

Just [3,4]

ghci> (:) <$> Just 3 <*> Just [4]

Just [3,4]

Вспомните, что оператор : – это функция, которая принимает элемент и список и возвращает новый список с этим элементом в начале. Теперь, когда у нас есть значение Just [3,4], могли бы ли мы объединить это со значением Just 2, чтобы произвести результат Just [2,3,4]? Да, могли бы. Похоже, мы можем сводить любое количество аппликативных значений в одно, которое содержит список результатов этих аппликативных значений.

Давайте попробуем реализовать функцию, которая принимает список аппликативных значений и возвращает аппликативное значение, которое содержит список в качестве своего результирующего значения. Назовём её sequenceA:

sequenceA :: (Applicative f) => [f a] –> f [a]

sequenceA [] = pure []

sequenceA (x:xs) = (:) <$> x <*> sequenceA xs

А-а-а, рекурсия! Прежде всего смотрим на тип. Он трансформирует список аппликативных значений в аппликативное значение со списком. После этого мы можем заложить некоторую основу для базового случая. Если мы хотим превратить пустой список в аппликативное значение со списком результатов, то просто помещаем пустой список в контекст по умолчанию. Теперь в дело вступает рекурсия. Если у нас есть список с «головой» и «хвостом» (вспомните, x – это аппликативное значение, а xs – это список, состоящий из них), мы вызываем функцию sequenceA с «хвостом», что возвращает аппликативное значение со списком внутри него. Затем мы просто предваряем значением, содержащимся внутри аппликативного значения x, список, находящийся внутри этого аппликативного значения, – вот именно!

Предположим, мы выполняем:

sequenceA [Just 1, Just 2]

По определению такая запись эквивалентна следующей:

(:) <$> Just 1 <*> sequenceA [Just 2]

Разбивая это далее, мы получаем:

(:) <$> Just 1 <*> ((:) <$> Just 2 <*> sequenceA [])

Мы знаем, что вызов выражения sequenceA [] оканчивается в виде Just [], поэтому данное выражение теперь выглядит следующим образом:

(:) <$> Just 1 <*> ((:) <$> Just 2 <*> Just [])

что аналогично этому:

(:) <$> Just 1 <*> Just [2]

…что равно Just [1,2]!

Другой способ реализации функции sequenceA – использование свёртки. Вспомните, что почти любая функция, где мы проходим по списку элемент за элементом и попутно накапливаем результат, может быть реализована с помощью свёртки:

sequenceA :: (Applicative f) => [f a] –> f [a]

sequenceA = foldr (liftA2 (:)) (pure [])

Мы проходим список с конца, начиная со значения аккумулятора равного pure []. Мы применяем функцию liftA2 (:) между аккумулятором и последним элементом списка, что даёт в результате аппликативное значение, содержащее одноэлементный список. Затем мы вызываем функцию liftA2 (:) с текущим в данный момент последним элементом и текущим аккумулятором и т. д., до тех пор пока у нас не останется только аккумулятор, который содержит список результатов всех аппликативных значений.

Давайте попробуем применить нашу функцию к каким-нибудь аппликативным значениям:

ghci> sequenceA [Just 3, Just 2, Just 1]

Just [3,2,1]

ghci> sequenceA [Just 3, Nothing, Just 1]

Nothing

ghci> sequenceA [(+3),(+2),(+1)] 3

[6,5,4]

ghci> sequenceA [[1,2,3],[4,5,6]]