[Haskell-cafe] Foldable, Traversable and choosing an order

[Tom Ellis]

On Mon, Sep 23, 2019 at 08:05:38PM +0100, Juan Casanova wrote:
> data SOTermPF fn p f = ConstF fn | Proj Int | CompF p [f] deriving Eq
> newtype SOTermF fn f = SOF (SOTermPF fn f f) deriving Eq
> 
> My Traversable instance (with comments on intermediate types because
> otherwise it can get pretty obscure):

Everyone else has made good comments, but to add a little and to be a little
more explicit: your data type uses [] so it makes sense to directly inherit
the Traversable (and hence Foldable) instance from that.  Your instance was
a little convoluted.  Here's what I would suggest:

    instance Foldable (SOTermF fn) where
      foldMap = foldMapDefault
    
    instance Traversable (SOTermF fn) where
      traverse f (SOF (ConstF c)) = pure (SOF (ConstF c))
      traverse f (SOF (Proj idx)) = pure (SOF (Proj idx))
      traverse f (SOF (CompF g sargs)) =
        SOF <$> (CompF <$> f g <*> traverse f sargs)