Implementing `sequenceA`

Question

I implemented sequenceA:

sequenceA :: Applicative f => [f a] -> f [a]
sequenceA []     = pure []
sequenceA (x:xs) = (++) <$> (fmap (\y -> [y]) x) <*> sequenceA xs

I don't like the fact that I'm making a new list, and then concatenating the result via ++.

However, I'm not sure how to make use of cons, i.e. :, in this function.

Please critique it.

Answer 1

The trick is to lift (:) into the applicative functor using pure thus getting an expression of type f (a -> [a] -> [a]) which you can then apply using (<*>). This gives you: sequenceA (x:xs) = pure (:) <*> x <*> sequenceA xs.

Now, the pattern pure ... <*> is equivalent to ... <$> so we can rewrite the previous equation to the shorter solution:

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

This pattern can be generalized to other datatypes: see the traversable typeclass. sequenceA can always be implemented for datatypes* by using pure to lift constructors and (<*>) to apply arguments (or induction hypotheses).

* strictly positive ones, at least

Answer 2

First, \y -> [y] is the same thing as Data.List.singleton, pure, and return. pure would probably fit the best since you’re already using Applicative. The parentheses surrounding the fmap are also unnecessary.

Second, you can rewrite this in terms of foldr:

sequenceA :: Applicative f => [f a] -> f [a]
sequenceA = foldr (\x rest -> (++) <$> fmap pure x <*> rest) (pure [])

Lastly, you say you don’t want to use ++. Fair enough. Use a difference list, then:

sequenceA :: Applicative f => [f a] -> f [a]
sequenceA = fmap ($ []) . foldr (\x rest -> (.) <$> fmap (:) x <*> rest) (pure id)