Learn You a Haskell for Great Good! - Miran Lipovaca [109]
sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA [] = pure []
sequenceA (x:xs) = (:) <$> x <*> sequenceA xs
Ah, recursion! First, we look at the type. It will transform a list of applicative values into an applicative value with a list. From that, we can lay some groundwork for a base case. If we want to turn an empty list into an applicative value with a list of results, we just put an empty list in a default context. Now comes the recursion. If we have a list with a head and a tail (remember that x is an applicative value and xs is a list of them), we call sequenceA on the tail, which results in an applicative value with a list inside. Then we just prepend the value inside the applicative x into that applicative with a list, and that’s it!
Suppose we do this:
sequenceA [Just 1, Just 2]}
By definition, that’s equal to the following:
(:) <$> Just 1 <*> sequenceA [Just 2]
Breaking this down further, we get this:
(:) <$> Just 1 <*> ((:) <$> Just 2 <*> sequenceA [])
We know that sequenceA [] ends up as being Just [], so this expression is now as follows:
(:) <$> Just 1 <*> ((:) <$> Just 2 <*> Just [])
which is this:
(:) <$> Just 1 <*> Just [2]
This equals Just [1,2]!
Another way to implement sequenceA is with a fold. Remember that pretty much any function where we go over a list element by element and accumulate a result along the way can be implemented with a fold:
sequenceA :: (Applicative f) => [f a] -> f [a]
sequenceA = foldr (liftA2 (:)) (pure [])
We approach the list from the right and start off with an accumulator value of pure []. We put liftA2 (:) between the accumulator and the last element of the list, which results in an applicative that has a singleton in it. Then we call liftA2 (:) with the now last element and the current accumulator and so on, until we’re left with just the accumulator, which holds a list of the results of all the applicatives.
Let’s give our function a whirl on some applicatives:
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],[]]
[]
When used on Maybe values, sequenceA creates a Maybe value with all the results inside it as a list. If one of the values is Nothing, then the result is also a Nothing. This is cool when you have a list of Maybe values, and you’re interested in the values only if none of them is a Nothing.
When used with functions, sequenceA takes a list of functions and returns a function that returns a list. In our example, we made a function that took a number as a parameter and applied it to each function in the list and then returned a list of results. sequenceA [(+3),(+2),(+1)] 3 will call (+3) with 3, (+2) with 3, and (+1) with 3, and present all those results as a list.
Doing (+) <$> (+3) <*> (*2) will create a function that takes a parameter, feeds it to both (+3) and (*2), and then calls + with those two results. In the same vein, it makes sense that sequenceA [(+3),(*2)] makes a function that takes a parameter and feeds it to all of the functions in the list. Instead of calling + with the results of the functions, a combination of : and pure [] is used to gather those results in a list, which is the result of that function.
Using sequenceA is useful when we have a list of functions and we want to feed the same input to all of them and then view the list of results. For instance, suppose that we have a number and we’re wondering whether it satisfies all of the predicates in a list. Here’s one way to do that:
ghci> map (\f -> f 7) [(>4),(<10),odd]
[True,True,True]
ghci> and $ map (\f -> f 7) [(>4),(<10),odd]
True
Remember that and takes a list of Booleans and returns True if they’re all True. Another way to achieve the same thing is with sequenceA:
ghci> sequenceA [(>4),(<10),odd] 7
[True,True,True]
ghci> and $ sequenceA [(>4),(<10),odd] 7
True
sequenceA