<blockquote>
  <p>The result type of the application f a has to be an applicative, why? Would a functor not be enough?</p>
</blockquote>

<p>This is a <em>fantastic</em> question. The original <a href="http://strictlypositive.org/Idiom.pdf" rel="noreferrer">McBride &amp; Paterson</a> paper goes in the other direction: it notices that a lot of computation are applicative in nature (can be rewritten with <code>pure</code> and <code>&lt;*&gt;</code>). <em>Then</em> it notices that certain containers, like <code>[]</code>, allow for a function of this type:</p>

<pre><code> idist :: Applicative f =&gt; [f a] -&gt; f [a]
 idist = ...
</code></pre>

<p>This we now call <code>sequence</code> in the <code>Traversable</code> class. All well and good, but it helps to probe the <em>strength</em> of our assumptions when we write abstractions. What if we tried to build a traversable library without <code>Applicative</code>, using only <code>Functor</code>? What exactly would go wrong?</p>

<h2>Products!</h2>

<p>For this it helps to read through the <a href="https://arxiv.org/pdf/1202.2919.pdf" rel="noreferrer">Jaskelioff &amp; Rypacek</a> paper that tries to pin down structures in category theory that correspond to applicative functors and traversable containers. The most interesting property of traversable containers is that they are <em>closed</em> under finite <em>sums</em> and <em>products</em>. This is great for Haskell programming, where a vast number of datatypes can be defined with sums and products:</p>

<pre><code>data WeirdSum a = ByList [a] | ByMaybe (Maybe a)

instance Traversable WeirdSum where
  traverse a2fb (ByList as) =
    ByList &lt;$&gt; traverse a2fb as
  traverse a2fb (ByMaybe maybeA) =
    ByMaybe &lt;$&gt; traverse a2fb maybeA
</code></pre>

<p>Ah, more evidence that we do not need all the power of Applicative! We are only using <code>fmap</code> here. Now finite products:</p>

<pre><code>data WeirdProduct a = WeirdProduct [a] (Maybe a)

instance Traversable WeirdProduct where
  traverse a2fb (WeirdProduct as aMaybe) =
    WeirdProduct &lt;$&gt; traverse a2fb as &lt;*&gt; traverse a2fb aMaybe
</code></pre>

<p>Here it is impossible to write a definition with <em>just</em> functors: <code>fmap</code> is great for sums but gives us no way to "glue" together two different functorial values. It is only with <code>&lt;*&gt;</code> that we are able to "close" traversable containers over finite products.</p>



<p>This is all well and good but lacks precision. We are sort of cherry-picking evidence here that <code>Functor</code> might be bad, but could we argue from first principles that <code>Applicative</code> is exactly what we need, no more and no less?</p>

<h2>Category theory!</h2>

<p>This problem is tackled in the second half of the Jaskelioff &amp; Rypacek paper. In category-theoretic terms, a functor <code>T</code> is traversable iff it allows for a family of natural transformations</p>

<pre><code>{ sequence | sequence : TFX -&gt; FTX, any applicative F }
</code></pre>

<p>where each natural transformation is "natural in F" and respects the "<a href="https://bartoszmilewski.com/2017/02/06/applicative-functors/" rel="noreferrer">monoidal structure of applicative functor composition</a>." It is that last phrase, that last little piece of jargon, where it is important to have <code>Applicative</code> rather than <code>Functor</code>. With <code>Applicative f</code>, we are able to glue together values of type <code>f a</code> and <code>f b</code>, where we either act on them (a la <code>foo &lt;$&gt; fa &lt;*&gt; fb</code> where <code>foo :: a -&gt; b -&gt; c</code> and <code>fa, fb :: f a, f b</code>) or just shove them into a tuple <code>f (a, b)</code>. This gives rise to the aforementioned "monoidal structure"; we need this to then prove that traversable functors are closed over finite products, just like we showed above. Without applicatives we couldn't even begin talking about how functors and products interact! If <strong>Hask</strong> is our category of Haskell types, then an applicative is just a way to name <strong>Hask</strong>-to-<strong>Hask</strong> endofunctors that "behave well" around <code>(-&gt;)</code> types and product types. </p>

<p>Hopefully this two-pronged answer, one in practical programming and one in categorical foo-foo, gives a little intuition as to why you want applicative functors when talking about traversability. I think often traversables are introduced with an element of magic around them, but they are very much motivated by practical concerns with solid theoretical foundations. Other language ecosystems may have easier-to-use iteration patterns and libraries, but I for one love the simplicity and elegance of <code>traverse</code> and <code>sequence</code>.</p>
The purpose of the Traversable typeclass
<p>Could someone please explain to me, what is the purpose of the typeclass <code>Traversable</code>?  </p>

<p>The typeclass definition is:</p>

<pre><code>class (Functor t, Foldable t) =&gt; Traversable (t :: * -&gt; *) where
</code></pre>

<p>So <code>Traversable</code> is a <code>Functor t</code> and <code>Foldable t</code>.  </p>

<p>The <code>traverse</code> function is a member of <code>Traversable</code> and has the following signature:  </p>

<pre><code>traverse :: Applicative f =&gt; (a -&gt; f b) -&gt; t a -&gt; f (t b)
</code></pre>

<p>Why does the result have to be wrapped into an applicative? What is the sense of it?   </p>

<p>I have the following example:</p>

<pre><code>module ExercisesTraversable where

  import Test.QuickCheck (Arbitrary, arbitrary)
  import Test.QuickCheck.Checkers (quickBatch, eq, (=-=), EqProp)
  import Test.QuickCheck.Classes (traversable)

  type TI = []

  newtype IdentityT a = IdentityT a
    deriving (Eq, Ord, Show)

  instance Functor IdentityT where
    fmap f (IdentityT a) = IdentityT (f a)

  instance Foldable IdentityT where
    foldMap f (IdentityT a) = f a

  instance Traversable IdentityT where
    traverse f (IdentityT a) = IdentityT &lt;$&gt; f a

  instance Arbitrary a =&gt; Arbitrary (IdentityT a) where
    arbitrary = do
      a &lt;- arbitrary
      return (IdentityT a)

  instance Eq a =&gt; EqProp (IdentityT a) where (=-=) = eq

  main = do
    let trigger = undefined :: TI (Int, Int, [Int])
    quickBatch (traversable trigger)  
</code></pre>

<p>Let's take a look at the <code>traverse</code> implementation:</p>

<pre><code>traverse f (IdentityT a) = IdentityT &lt;$&gt; f a
</code></pre>

<p>The result type of the application <code>f a</code> has to be an applicative, why? Would a functor not be enough?</p>