Context bounds in Traversable1

Question

In semigroupoids package I found the following definition:

class (Foldable1 t, Traversable t) => Traversable1 t where
  traverse1 :: Apply f => (a -> f b) -> t a -> f (t b)
  sequence1 :: Apply f => t (f b) -> f (t b)

  sequence1 = traverse1 id
  traverse1 f = sequence1 . fmap f

Why are the context bounds set to Apply (an Applicative without pure) and not to Functor? Obviously you need to overwrite one of the definitions, so is this impossible with "just" a Functor?

Answer 1

This is just a slightly tightened definition of a Traversable---all Traversable1s are Traversable, but not visa versa. For many (many) more details on why Traversables need Applicatives, it's worth taking a look at Applicative Programming with Effects perhaps. Gesturally, if you just had a Functor it wouldn't be possible to "sequence" the effects of that functor should it contain many values since your "injection" function (a -> f b) is the only way to get bs and you can't join the layers of your f.

But, broadly, when you define Traversables you only need to use the effect-free injection function, pure, for "default" values, which is exactly what Traversable1 eliminates. That's why NonEmpty is an instance but [] isn't.

To make things concrete, consider these example instances for the identity functor, Maybe, NonEmpty lists, and regular [].

newtype Id a = Id a
instance Functor Id where fmap f (Id a) = Id (f a)

instance Applicative Id where
  pure = Id
  (Id f) <*> (Id x) = Id (f x)

We only need a Functor instance here exactly because Id has only one element and no "default" branch—it's quite trivial.

instance Traversable Id where traverse inj (Id a) = Id <$> inj a
instance Traversable1 Id where traverse1 inj (Id a) = Id <$> inj a

We need pure for the "default" Nothing case of Maybe (which is only slightly more complex than Id).

instance Traversable Maybe where
  traverse _ Nothing = pure Nothing
  traverse inj (Just a) = Just <$> inj a

instance Traversable1 Maybe can't exist because Maybe has a default branch; we see this because we can't use pure if we only have an Apply constraint.

data NonEmpty a = NonEmpty a [a]

instance Functor NonEmpty where fmap f (NonEmpty a as) = NonEmpty (f a) (fmap f as)

instance Apply NonEmpty where
  (NonEmpty f fs) <.> (NonEmpty x xs) = NonEmpty (f x) (fs <*> xs)

instance Pointed NonEmpty where
  point a = NonEmpty a []

instance Applicative NonEmpty where
  (<*>) = (<.>)
  pure = point

instance Traversable NonEmpty where
  traverse inj (NonEmpty a as) = NonEmpty <$> inj a <*> (traverse inj a as)

and since we only used (<*>) and not pure, we can make this a Traversable1 instance

instance Traversable1 NonEmpty where
  traverse1 inj (NonEmpty a []) = (`NonEmpty` []) <$> inj a
  traverse1 inj (NonEmpty a (b: bs)) = 
    (\a' (NonEmpty b' bs') -> NonEmpty a' (b': bs')) 
    <$> inj a 
    <.> traverse1 inj (NonEmpty b bs)

but this doesn't work for [] since we end up using pure for the "default" branch

instance Traversable [] where
  traverse _   []     = pure []
  traverse inj (x:xs) = (:) <$> inj x <*> traverse inj xs

---

Edit: Originally I had played fast and loose with my definition of Traversable1 NonEmpty. The current version actually works but is a lot harder on the eyes. Previously I tried traversing the inner list, which works in spirit because the [] in the second slot of NonEmpty has the first slot to help it, but that can't work directly since the inner list has an empty case [] which needs pure. Instead, we have to avoid that empty case by "stealing" the always existant a in the first position and then replacing it after the traverse.

That method (and datatype definition) is very similar to the versions used in the Semigroups and Semigroupoids libraries themselves and are useful since they can take advantage of library momentum behind regular [], but if we define NonEmpty a little differently we can see that there's a great deal of parallelism between Traversable and Traversable1. The fact that a Traversable1 instance can exist is truly a feature of the data type alone---the definitions are basically identical.

import Data.Monoid
import qualified Data.Semigroup as Se
import Data.Traversable
import Data.Foldable
import Data.Semigroup.Foldable
import Data.Semigroup.Traversable
import Data.Functor.Apply
import Control.Applicative

-- For comparison
data List     a = Empty | List a (List     a)
data NonEmpty a = One a | Many a (NonEmpty a)

instance Functor NonEmpty where
  fmap f (One a) = One (f a)
  fmap f (Many a as) = Many (f a) (fmap f as)

instance Apply NonEmpty where
  (One f) <.> (One a)         = One (f a)
  (One f) <.> (Many a _)      = One (f a)
  (Many f _) <.> (One a)      = One (f a)
  (Many f fs) <.> (Many a as) = Many (f a) (fs <.> as)

instance Applicative NonEmpty where
  pure = One
  (<*>) = (<.>)

instance Foldable NonEmpty where
  foldMap f (One a) = f a
  foldMap f (Many a as) = f a <> foldMap f as

instance Foldable1 NonEmpty where
  foldMap1 f (One a) = f a
  -- Core distinction: we use the Semigroup.<> instead of the Monoid.<>
  foldMap1 f (Many a as) = f a Se.<> foldMap1 f as

instance Traversable NonEmpty where
  traverse inj (One a) = One <$> inj a
  traverse inj (Many a as) = Many <$> inj a <*> traverse inj as

instance Traversable1 NonEmpty where
  traverse1 inj (One a) = One <$> inj a
  traverse1 inj (Many a as) = Many <$> inj a <.> traverse1 inj as