Explain the implementation of Traverse [List] in scalaz-seven

Question

I am trying to understand the implementation of traverseImpl 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 List interacts with Applicative ? Ultimately, I would like to be able to implement other instances for Traverse .

Answer 1

Applicability allows you to apply a function in a context to a value in a context. For example, you can apply some((i: Int) => i + 1) to some(3) and get some(4) . Forget it now. I will come back to this later.

The list has two views: either Nil or head :: tail . You can use it to fold with foldLeft , but there is another way to fold 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 add up the list using a function starting on the right side - although we do deconstruct the list on the left side!

 f(1, f(2, Nil)) 

This can be used to calculate the length of the 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, for an empty list and function :: we managed to create another list. What if our elements are in some context? If our context is applicative, we can still apply our elements and :: in this context. Continuing List(1, 2) and Option as our application. Let's start with some(List[Int]())) , we want to use the :: function in the context of Option . This is what F.map2 does. It takes two values ​​in the Option context, puts the provided function of the two arguments in the Option context, and applies them together.

So, out of context, we have (2, Nil) => 2 :: Nil

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

Returning 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'm not sure why the DList difference is DList . I see that he uses trampolines so reliably that makes this implementation work without blowing the stack, but I have not tried it, so I don’t know.

The interesting part about implementing the correct fold like this is that I think it gives you an approach to implementing a traverse for algebraic data types using catamorphisms ,

For example:

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

Fold will be defined as follows (which really corresponds to 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 the traverse will use this fold with F.point(Leaf) and apply it to Node.apply . Although there is no F.map3 , so it can be a little cumbersome.

Answer 2

This is not so easy to understand. I recommend reading the article related at the beginning of my related blog post .

I also made a presentation on this subject during the last meeting on functional programming in Sydney, and you can find slides here .

If I try to explain in a few words, traverse will move through each element of the list one by one, eventually rebuild the list (_ :: _) , but accumulate / execute some kind of “effects” as given by F Applicative . If F State , it keeps track of some state. If F is applicative, corresponding to a Monoid , it aggregates some measure for each element of the list.

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

From there, you see that the implementation of other traverse instances is only related to apply with the data constructors of the data structure that you want to cross. If you look at the associated PowerPoint presentation, you will see several slides that walk around the binary tree.

Answer 3

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

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

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

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