Traversals in depth

The Partial Lenses Implementation document should also be helpful for understanding traversals.

In the PL library, a traversal is a function with the following signature:

(Maybe s, Index, Applicative c, (Maybe a, Index) -> c b) -> c t

Let's open that up:

(
  // An optional data structure to operate on:
  Maybe s,

  // An (optional) informational index to pass along:
  Index,

  // A Static Land applicative to build the operation with:
  Applicative c,

  // A function to map a targeted (optional) element
  // and index to an operation in the applicative:
  (Maybe a, Index) -> c b
)
// The end result is the applicative operation built by
// the traversal:
-> c t

So, what a traversal does is that it builds an operation. For example, suppose you'd use L.elems on the list ['a', 'b'] with applicative A and function toA. The operation that gets built ends up looking a bit like this:

A.ap(A.map(R.prepend,
           toA('a', 0)),
     A.ap(A.map(R.prepend,
                toA('b', 1))
          A.of([])))

What that does is that it indeed maps the elements of the list ['a', 'b'] to operations using the given toA function. It then uses the operations of the applicative A, namely of, map, and ap, to build an operation that creates a list with the same structure as the original list, but using the results that the operations returned by toA produce.

What operations on traversals, like collect and modify and all the rest, do is that they call the traversal function with an appropriate applicative and a function to map targeted elements to the applicative. The traversal then builds the operation. Finally the operation is executed, returning the desired end result, which might be a new data structure or something computed from the elements targeted by the traversal.

In the case of collect the applicative operations, of, map, and ap, actually kind of ignore their arguments:

const CollectA = {
  of: _ => [],
  map: (_, result) => result,
  ap: (lhs, rhs) => [].concat(lhs, rhs)
}

In this case there is no need to separately execute the operation, because it directly computes the end result we want.

Here is the above as a playground.

The current internal implementation of collect in PL is quite different from the above discussion, because it has been heavily optimized taking advantage of internal implementation details. (The library provided version of collect also ignores undefined elements.)

Some more examples of traversals:

• updating a tree