How does sequenceA work on lists of pairs?

user_5825294 0
Viewed 202

Spin off of this question. Intuitively I have understood what sequenceA does in that usecase, but not how/why it works like that.

So it all boils down to this question: how does sequenceA work in the following case?

> sequenceA [("a",1),("b",2),("c",3)]
("abc",[1,2,3])

I see that

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

so in the usecase above the Traversable is [], and the Applicative, since (,) is a binary type constructor, is (,) a, which means that the pair is taken as an applicative functor on its snd field. And this goes together the list ending up in the snd of the result. So we go from a list of pairs to a pair with a list in its second field.

But where does the "abc" come from? I mean, I know that it's the concatenation of the fst of all the pairs, but I don't know if it's via ++ or via concat of the list of the fsts. There seems to be nothing in sequenceA's signature to enforce that the fsts of the pairs can be combined together.

Still that assumption has to be used somewhere. Indeed, the following fails

sequenceA [('a',1),('b',2),('c',3)]
applicative haskell
2 Answers

It uses mappend. The Applicative instance it uses looks like this:

instance Monoid a => Applicative ((,) a) where
    pure x = (mempty, x)
    (af, f) <*> (ax, x) = (mappend af ax, f x)
user_7916040

In Haskell, typeclass instances for a type can be "conditional" on the existence of other typeclass instances for parts of the type. Not all type constructors of the form ((,) a)are instances of Applicative, but only those for which the a type has a Monoid instance.

These required constraints appear before the => in the instance's Haddocks, like this:

Monoid a => Applicative ((,) a)

Why is the Monoid instance required? For one, pure for ((,) a) needs to materialize an a value out of thin air to put in the first element of the tuple. mempty for the type a does the job.

There can be chains of required constraints that are several levels deep. For example, why does the following work?

ghci> import Datta.Function ((&)) -- flipped application
ghci> [(id :: String -> String, 2 :: Int), (\x -> x ++ x, 1)] & sequenceA & fst $ "foo"
"foofoofoo"

Here the first component is a function. As before, it must have a Monoid instance for the sequenceA to work. But when is the type a -> b a Monoid? Looking at the Haddocks, we find:

Monoid b => Monoid (a -> b)

That is, functions are Monoids when the return type (here String) is a Monoid.

Actually, there's another Monoid instance for functions available through the Endo newtype. It's common to use newtypes to select which instance to use for a given operation, although it requires some amount of wrapping and unwrapping.

user_13642880
Related