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
.
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.
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 apply
ing 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With