Reverse instance for generic type

Question

I am completely stuck in this exercise from the excellent Haskell Programming book.

Given the following new type for compiling Functor and Applicative type and instances, write an instance of Traversable (Compose fg) .

 newtype Compose fga = Compose { getCompose :: f (ga) } deriving (Eq, Show) instance (Functor f, Functor g) => Functor (Compose fg) where fmap f (Compose fga) = Compose $ (fmap . fmap) f fga instance (Applicative f, Applicative g) => Applicative (Compose fg) where pure = Compose <$> pure . pure Compose f <*> Compose x = Compose $ ((<*>) <$> f) <*> x 

My proposed solution looks like it should work, depending on the type of traverse.traverse , but ghci complains. I have a vague feeling that this is due to repackaging in the Compose constructor:

 instance (Traversable f, Traversable g) => Traversable (Compose fg) where traverse f1 (Compose fga) = (traverse.traverse) f1 fga 

gives an error like:

 composing_types.hs:69:31: Couldn't match type 'b' with 'g b' 'b' is a rigid type variable bound by the type signature for traverse :: Applicative f1 => (a -> f1 b) -> Compose fga -> f1 (Compose fgb) at composing_types.hs:69:3 Expected type: f1 (Compose fgb) Actual type: f1 (Compose fg (gb)) Relevant bindings include fga :: f (ga) (bound at composing_types.hs:69:24) f1 :: a -> f1 b (bound at composing_types.hs:69:12) traverse :: (a -> f1 b) -> Compose fga -> f1 (Compose fgb) (bound at composing_types.hs:69:3) In the expression: (traverse . traverse) f1 fga In an equation for 'traverse': traverse f1 (Compose fga) = (traverse . traverse) f1 fga composing_types.hs:69:54: Couldn't match type 'f' with 'Compose f g' 'f' is a rigid type variable bound by the instance declaration at composing_types.hs:68:10 Expected type: Compose fg (ga) Actual type: f (ga) Relevant bindings include fga :: f (ga) (bound at composing_types.hs:69:24) traverse :: (a -> f1 b) -> Compose fga -> f1 (Compose fgb) (bound at composing_types.hs:69:3) In the second argument of 'traverse . traverse', namely 'fga' In the expression: (traverse . traverse) f1 fga 

Answer 1

Holes

This is another great question that can be solved with the help of leaky expressions.

First, suppose we have already defined Foldable instances.

 λ> instance (Foldable f, Foldable g) => Foldable (Compose fg) where foldr = undefined 

Next, an instance of Traversable. Match the pattern in the Compose argument because you know what you have to do, but leave everything else in the hole otherwise.

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = _ tua 

GHC will help to throw out an error -

 <interactive>:...:... Found hole '_' with type: f (Compose tub) 

- in addition to the types of all variables in the field.

 Relevant bindings include tua :: t (ua) (bound at ...) a2fb :: a -> fb (bound at ...) traverse :: (a -> fb) -> Compose tua -> f (Compose tub) (bound at ...) 

(I chose the names of types and values ​​so that everything is neat. Do not pay attention to the person behind the curtain.) Now the question is about the hour: how to call the value f (Compose tub) , taking into account everything else, We know

• The only way to build a Compose tub is to create a t (ub) value.

• It is not possible to create the value of f anything except (1) pure and (2) fmap , and we know that we cannot use pure because we are trying to collect the “side effects” of a2fb :: a -> fb here.

This leads us to the next blow to the solution.

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = fmap Compose (_ tua) <interactive>:... Found hole '_' with type: t (ua) -> f (t (ub)) 

Finally, we have a t . We know that t is Traversable, so try going through it.

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = fmap Compose ((\tua -> traverse _ tua) tua) <interactive>:56:138: Found hole '_' with type: ua -> f (ub) 

The same deal. We know u is Traversable, so try going through it.

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = fmap Compose ((\tua -> traverse (\ua -> traverse _ ua) tua) tua) <interactive>:57:155: Found hole '_' with type: a -> fb 

Tin hole for our a2fb .

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = fmap Compose ((\tua -> traverse (\ua -> traverse a2fb ua) tua) tua) 

Eta-reduce to cut lambdas and you get a solution .

 λ> instance (Traversable t, Traversable u) => Traversable (Compose tu) where traverse a2fb (Compose tua) = fmap Compose (traverse (traverse a2fb) tua)