Explain Traverse[List] implementation in scalaz-seven

Question

I'm trying to understand the traverseImpl implementation in scalaz-seven:

def traverseImpl[F[_], A, B](l: List[A])(f: A => F[B])(implicit F: Applicative[F]) = {
  DList.fromList(l).foldr(F.point(List[B]())) {
     (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  }
}

Can someone explain how the List interacts with the Applicative? Ultimately, I'd like to be able to implement other instances for Traverse.

Answer 1

An applicative lets you apply a function in a context to a value in a context. So for instance, you can apply some((i: Int) => i + 1) to some(3) and get some(4). Let's forget that for now. I'll come back to that later.

List has two representations, it's either Nil or head :: tail. You may be used to fold over it using foldLeft but there is another way to fold over it:

def foldr[A, B](l: List[A], acc0: B, f: (A, B) => B): B = l match {
   case Nil => acc0
   case x :: xs => f(x, foldr(xs, acc0, f))
}

Given List(1, 2) we fold over the list applying the function starting from the right side - even though we really deconstruct the list from the left side!

f(1, f(2, Nil))

This can be used to compute the length of a list. Given List(1, 2):

foldr(List(1, 2), 0, (i: Int, acc: Int) => 1 + acc)
// returns 2

This can also be used to create another list:

foldr[Int, List[Int]](List(1, 2), List[Int](), _ :: _)
//List[Int] = List(1, 2)

So given an empty list and the :: function we were able to create another list. What if our elements are in some context? If our context is an applicative then we can still apply our elements and :: in that context. Continuing with List(1, 2) and Option as our applicative. We start with some(List[Int]())) we want to apply the :: function in the Option context. This is what the F.map2 does. It takes two values in their Option context, put the provided function of two arguments into the Option context and apply them together.

So outside the context we have (2, Nil) => 2 :: Nil

In context we have: (Some(2), Some(Nil)) => Some(2 :: Nil)

Going back to the original question:

// do a foldr 
DList.fromList(l).foldr(F.point(List[B]())) {
  // starting with an empty list in its applicative context F.point(List[B]())
  (a, fbs) => F.map2(f(a), fbs)(_ :: _)
  // Apply the `::` function to the two values in the context
}

I am not sure why the difference DList is used. What I see is that it uses trampolines so hopefully that makes this implementation work without blowing the stack, but I have not tried so I don't know.

The interesting part about implementing the right fold like this is that I think it gives you an approach to implement traverse for algebric data types using catamorphisms.

For instance given:

trait Tree[+A]
object Leaf extends Tree[Nothing]
case class Node[A](a: A, left: Tree[A], right: Tree[A]) extends Tree[A]

Fold would be defined like this (which is really following the same approach as for List):

def fold[A, B](tree: Tree[A], valueForLeaf: B, functionForNode: (A, B, B) => B): B = {
  tree match {
    case Leaf => valueForLeaf
    case Node(a, left, right) => functionForNode(a, 
        fold(left, valueForLeaf, functionForNode), 
        fold(right, valueForLeaf, functionForNode)
      )
  }
}

And traverse would use that fold with F.point(Leaf) and apply it to Node.apply. Though there is no F.map3 so it may be a bit cumbersome.

Answer 2

This not something so easy to grasp. I recommend reading the article linked at the beginning of my blog post on the subject.

I also did a presentation on the subject during the last Functional Programming meeting in Sydney and you can find the slides here.

If I can try to explain in a few words, traverse is going to traverse each element of the list one by one, eventually re-constructing the list (_ :: _) but accumulating/executing some kind of "effects" as given by the F Applicative. If F is State it keeps track of some state. If F is the applicative corresponding to a Monoid it aggregates some kind of measure for each element of the list.

The main interaction of the list and the applicative is with the map2 application where it receives a F[B] element and attach it to the other F[List[B]] elements by definition of F as an Applicative and the use of the List constructor :: as the specific function to apply.

From there you see that implementing other instances of Traverse is only about applying the data constructors of the data structure you want to traverse. If you have a look at the linked powerpoint presentation, you'll see some slides with a binary tree traversal.

Answer 3

List#foldRight blows the stack for large lists. Try this in a REPL:

List.range(0, 10000).foldRight(())((a, b) => ())

Typically, you can reverse the list, use foldLeft, then reverse the result to avoid this problem. But with traverse we really have to process the elements in the correct order, to make sure that the effect is treated correctly. DList is a convenient way to do this, by virtue of trampolining.

In the end, these tests must pass:

https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/TraverseTest.scala#L13 https://github.com/scalaz/scalaz/blob/scalaz-seven/tests/src/test/scala/scalaz/std/ListTest.scala#L11 https://github.com/scalaz/scalaz/blob/scalaz-seven/core/src/main/scala/scalaz/Traverse.scala#L76