Implementing `traverse` and `sequenceA`

Question

I'm trying to implement traverse and sequenceA on my own:

Here's my implementation of traverse' in terms of sequenceA:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' f x = sequenceA' $ fmap f x 

However, I'm stuck on implementing sequenceA.

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' x = foldr (\a _ -> fmap helper a) (error "...") x

I used a placeholder for b (error "...") - I'm not sure how to create a b given these types.

helper :: (Functor t, Foldable t) => a -> t a
helper x = error "TODO"

Also, I used the helper function to get this code to type-check. But, again, that's simply an error call. Please give me a hint on how to generically implement sequenceA.

Answer 1

Given:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb ta = sequenceA' (fmap a2fb ta)

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = _

An ideal use of holes! We give a name to all our parameters (no need to go pointfree and make our lives difficult just quite yet) and stick a hole where a definition should be. This yields:

src/Main.hs:8:14: Found hole ‘_’ with type: f (t a) …

We now cast around for a function that returns something like f (t a). As luck would have it, traverse' does and now we can refine our hole to:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse _ _

src/Main.hs:8:27: Found hole ‘_’ with type: a0 -> f a …
src/Main.hs:8:29: Found hole ‘_’ with type: t a0 …

That first one looks messy, but we know something that fits the t a0 for the second one, which is our tfa. Plug and chug:

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse _ tfa

src/Main.hs:8:27: Found hole ‘_’ with type: f a -> f a …

Well, we know of a function with that signature, and that's id. So our final answer is:

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb ta = sequenceA' (fmap a2fb ta)

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' tfa = traverse id tfa

We can now go young, wild, and pointfree(-ish):

traverse' :: (Functor t, Foldable t, Applicative f) => (a -> f b) -> t a -> f (t b)
traverse' a2fb = sequenceA' . fmap a2fb

sequenceA' :: (Functor t, Foldable t, Applicative f) => t (f a) -> f (t a)
sequenceA' = traverse id

Which matches the definitions in Prelude. ~holes~