This is just a slightly concise definition of Traversable --- all Traversable1 Traversable , but not vice versa. For many (more) details about why Traversable needs Applicative s, take a look at Applicative Programming with Effects . Gesturally, if you just had a Functor , it would be impossible to act on this functor sequentially if it contains many values, since your injection function (a -> fb) is the only way to get b , and you cannot join layers of your f .
But in a broad sense, when you define Traversable , you need to use the no-effect function, pure , for the default values, which exactly excludes Traversable1 . Therefore NonEmpty is an instance, but [] not.
To do specific things, consider these examples of instances for the identity functor, Maybe , NonEmpty and regular [] lists.
newtype Id a = Id a instance Functor Id where fmap f (Id a) = Id (fa) instance Applicative Id where pure = Id (Id f) <*> (Id x) = Id (fx)
We only need an instance of Functor , because Id has only one element and does not have a default branch - this is pretty 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 case of Nothing Maybe (which is a bit more complicated than Id ).
instance Traversable Maybe where traverse _ Nothing = pure Nothing traverse inj (Just a) = Just <$> inj a
instance Traversable1 Maybe cannot exist because Maybe has a default branch; we see this because we cannot use pure if we have an Apply constraint.
data NonEmpty a = NonEmpty a [a] instance Functor NonEmpty where fmap f (NonEmpty a as) = NonEmpty (fa) (fmap f as) instance Apply NonEmpty where (NonEmpty f fs) <.> (NonEmpty x xs) = NonEmpty (fx) (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 used only (<*>) and not pure , we can make this instance of Traversable1
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 does not work for [] , since we use pure for the "default" branch
instance Traversable [] where traverse _ [] = pure [] traverse inj (x:xs) = (:) <$> inj x <*> traverse inj xs
Edit: Initially, I played quickly and freely with my definition of Traversable1 NonEmpty . The current version actually works, but is much more complicated before our eyes. I used to try traversing internal list, which works like that because [] in the second slot NonEmpty has the first slot that can help it, but it cannot work directly, because the internal list has an empty case [] that needs pure . Instead, we should avoid this empty case by "stealing" the always existing a in the first position, and then replacing it after the traverse.
This method (and data type determination) is very similar to the versions used in the Semigroups and Semigroupoids libraries themselves, and is useful because they can use the library momentum behind the regular [] , but if we define NonEmpty little differently, we can see that between Traversable and Traversable1 there is a large amount of parallelism. The fact that an instance of Traversable1 can exist is really a feature of the data type only - 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 (fa) fmap f (Many a as) = Many (fa) (fmap f as) instance Apply NonEmpty where (One f) <.> (One a) = One (fa) (One f) <.> (Many a _) = One (fa) (Many f _) <.> (One a) = One (fa) (Many f fs) <.> (Many a as) = Many (fa) (fs <.> as) instance Applicative NonEmpty where pure = One (<*>) = (<.>) instance Foldable NonEmpty where foldMap f (One a) = fa foldMap f (Many a as) = fa <> foldMap f as instance Foldable1 NonEmpty where foldMap1 f (One a) = fa -- Core distinction: we use the Semigroup.<> instead of the Monoid.<> foldMap1 f (Many a as) = fa 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