Миран Липовача - Изучай Haskell во имя добра!

Есть интересная концепция: мы можем взять два аппликативных значения и свести их в одно, которое содержит в себе результаты этих двух аппликативных значений в списке. Например, у нас есть значения 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]]

[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

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

[]

При использовании со значениями типа Maybeфункция sequenceAсоздаёт значение типа Maybe, содержащее все результаты в виде списка. Если одно из значений равно Nothing, результатом тоже является Nothing. Это просто расчудесно, когда у вас есть список значений типа Maybeи вы заинтересованы в значениях, только когда ни одно из них не равно Nothing!

В применении к функциям sequenceAпринимает список функций и возвращает функцию, которая возвращает список. В нашем примере мы создали функцию, которая приняла число в качестве параметра и применила его к каждой функции в списке, а затем вернула список результатов. Функция sequenceA [(+3),(+2),(+1)] 3вызовет функцию (+3)с параметром 3, (+2)– с параметром 3и (+1)– с параметром 3и вернёт все эти результаты в виде списка.