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

liftA2 :: (Applicative f) => (a –> b –> c) –> f a –> f b –> f c

Она определена вот так:

liftA2 :: (Applicative f) => (a –> b –> c) –> f a –> f b –> f c

liftA2 f a b = f <$> a <*> b

Она просто применяет функцию между двумя аппликативными значениями, скрывая при этом аппликативный стиль, который мы обсуждали. Однако она ясно демонстрирует, почему аппликативные функторы более мощны по сравнению с обычными.

При использовании обычных функторов мы можем просто отображать одно значение функтора с помощью функций. При использовании аппликативных функторов мы можем применять функцию между несколькими значениями функторов. Интересно также рассматривать тип этой функции в виде (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]]

[[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 и вернёт все эти результаты в виде списка.

Выполнение выражения (+) <$> (+3) <*> (*2) создаст функцию, которая принимает параметр, передаёт его и функции (+3) и (*2), а затем вызывает оператор + с этими двумя результатами. Соответственно, есть смысл в том, что выражение sequenceA [(+3),(*2)] создаёт функцию, которая принимает параметр и передаёт его всем функциям в списке. Вместо вызова оператора + с результатами функций используется сочетание : и pure [] для накопления этих результатов в список, который является результатом этой функции.

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

ghci> map (f –> f 7) [(>4),(<10),odd]

[True,True,True]

ghci> and $ map (f –> f 7) [(>4),(<10),odd]

True

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

ghci> sequenceA [(>4),(<10),odd] 7

[True,True,True]

ghci> and $ sequenceA [(>4),(<10),odd] 7

True

Выражение sequenceA [(>4),(<10),odd] создаёт функцию, которая примет число, передаст его всем предикатам в списке [(>4),(<10),odd] и вернёт список булевых значений. Она превращает список с типом (Num a) => [a –> Bool] в функцию с типом (Num a) => a –> [Bool]. Правда, клёво, а?

Поскольку списки однородны, все функции в списке должны быть одного и того же типа, конечно же. Вы не можете получить список вроде [ord, (+3)], потому что функция ord принимает символ и возвращает число, тогда как функция (+3) принимает число и возвращает число.

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

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> [[x,y] | x <– [1,2,3], y <– [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]]

[[1,3],[1,4],[2,3],[2,4]]

ghci> [[x,y] | x <– [1,2], y <– [3,4]]

[[1,3],[1,4],[2,3],[2,4]]

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

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

ghci> [[x,y,z] | x <– [1,2], y <– [3,4], z <– [5,6]]

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

Выражение (+) <$> [1,2] <*> [4,5,6] возвращает в результате недетерминированное вычисление x + y, где образец x принимает каждое значение из [1,2], а y принимает каждое значение из [4,5,6]. Мы представляем это в виде списка, который содержит все возможные результаты. Аналогичным образом, когда мы выполняем выражение sequenceA [[1,2],[3,4],[5,6]], результатом является недетерминированное вычисление [x,y,z], где образец x принимает каждое значение из [1,2], а y – каждое значение из [3,4] и т. д. Для представления результата этого недетерминированного вычисления мы используем список, где каждый элемент в списке является одним возможным списком. Вот почему результатом является список списков.