Why Traversable Requires Applicative at Least¶

At the beginning, the blog name is why traversable requires applicative. However, later I feel like it is nonsense and just repeating the sentence to describe the traversable. It requires applicative of course because it uses that. As a result, I changed blog name because in this blog, we will learn about how the traversable uses applicative and why it requires applicative at least.

You should be familiar with Foldable before reading this blog, and I recommend you to read my previous blog why foldable requires monoid at least

In short, applicative is needed as we need to lift the chosen operator, pure the default value and keep applying by Foldable function foldr.

Traversable Typeclass¶

Traversable has more constraints than foldable. The typeclass Traversable requires either function traverse or function sequenceA.
In this blog, we discuss the traverse function implementation only.

class (Functor t, Foldable t) => Traversable (t :: Type -> Type) where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)

Recall that the foldable supports both foldMap and foldr. However, in the traversable, we use foldr only as the f is not a monoid(functor isn't a monoid in haskell).

The type constraints are necessary because:

Functor t is needed because we need its data constructor
Foldable t is needed because we need its foldr to fold the t.
Applicative f is needed because we need:
pure to construct default value
lift(liftA2 e.g) the operator to combine data

Simple Traversable: Maybe¶

The Traversable Maybe is a very simple traversable, and it even doesn't use the functionality of applicative f. Because each Maybe holds only one value, we don't have the opportunity to use apply.

instance Traversable Maybe where
    traverse _ Nothing = pure Nothing
    traverse f (Just x) = Just <$> f x

Traversable: List¶

Differ than Maybe, the Foldable List [] will choose an operator to lift and apply to the elements.

The code snippet below prints [1,2,3] in the console.

main :: IO ()
main = do
    print $ foldMap (\x-> [x,x+1,x+2]) $ Just 1
    -- output: [1,2,3]

It simply uses the foldr to fold the Foldable t. The initial value is created by pure operation along with the initial value of [], which is pre-defined by the applicative functor designer. The initial value has type f (t a).

The function f will fmap each element, then we use the lifted operator to apply it with the initial value to get a new value with f (t a). Note that the operator is chosen by traversable designer, for example, the operator chosen by List designer is (:).

By keep applying the new value with fmaped value with the help of foldr, we finish to traverse all element from a Foldable t.

The implementation of Traversable [] conveys this idea as well, as the source code shows below.

instance Traversable [] where
    {-# INLINE traverse #-} -- so that traverse can fuse
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = liftA2 (:) (f x) ys

Example: Reversed List¶

To better understand traversable, we can implement one to ensure our thought follows the correct way. Here, we want to define a reversed List, where during traversing it will put the first last, and the last first.

First of all, we need to make RList is instances of Functor and Applicative Functor. We won't implement foldMap for RList because we have no monoid to do in the traversable side. Instead, we implement foldr as we need it.

newtype RList a = RList {
  list :: [a]
} deriving Show

instance Functor RList where
  fmap f (RList xs) = RList $ fmap f xs

instance Applicative RList where
  pure x = RList [x]
  (<*>) (RList fs) (RList xs) = RList (fs <*> xs)

instance Foldable RList where
  foldr :: (a -> b -> b) -> b -> RList a -> b
  foldr f x (RList xs) = foldr f x xs

Then, we define a custom function rotate' as the operator to apply elements, and it's so-called 'operator chosen by designer'. Then, we use the same idea to pure the initial value, fmap the element, lift the operator and apply them together. That's all to implement a traversable.

rotate' :: RList a -> RList a -> RList a
rotate' (RList a) (RList b) = RList $ b++a

instance Traversable RList where
  traverse::Applicative f => (a -> f b) -> RList a -> f (RList b)
  traverse f (RList xs) = foldr f1 initial xs where
    -- liftA2 is a syntax for applicative functor applying,
    -- the same expression is:
    -- f1 x acc= (\y RList ys) -> rotate' (RList [y]) (RList ys)) <$> f x <*> acc
    f1 = liftA2 (\y (RList ys) -> rotate' (RList [y]) (RList ys)) . f
    initial = pure (RList [])

We can run it to verify our RList works as expected. The output will be [RList {list = [4,3,2]}], which satisfy our expectation.

main :: IO ()
main = do
    print $ traverse (\x->[x,x,x]) (RList [1])