Traversable

Traversable

interface Traversable[T]
{
   traverse    [F : Applicative, A]                   : (T -> F[A]) -> F[Sub[A]]
   traverse    [F : Applicative, A]                   : (T -> F[A]?) -> F[Sub[A]]

   static dist [R : Traversable, F : Applicative, T]  : R[F[T]] -> F[R[T]]
      = r -> r.traverse( x -> x )
}

Synopsis

The method traverse returns the equivalent output of both a Foldable.fold and a Functor.map in a single walk of any T instances contained in the subtype Sub[T] of Traversable. The fold can operate on the value before and/or after the implied morphism

:
      T -> A

.

Instead of returning in a 2-tuple as case-specific boilerplate could do, these results are embedded idiomatically (to the category theory) so as to maximize generality.

If the morphism function of type : T -> F[A]? returns None, the walk will terminate prematurely, but only if it makes sense for the semantics of the subtype Sub of Traversable.

Rationale

Without traverse, folding to some accumulated result on each element of a List[T], while mapping to a List[A], would either require walking the list twice, or it would require access inside a single fold to a MonoidLifted interface to accumulate the mapped list. In the latter case of a single fold where the only computed result is the mapped list, the functionality is already provided by Functor.mapFold.

Whereas, traverse is generalized to any Traversable, so the code does not have to specialize on various specific-cases of mapping between different types, e.g. mapping List[T] to a Maybe[A].

Reuse of code (without boilerplate) is greatly improved. Functional programming (FP) echews repeating oneself.

To conceptualize the efficiency gained over a Functor. If given that Sub[T] is a subtype of both Functor and Traversable, then employing the morphism function of type : T -> F[A], the Functor.map method returns the type Sub[F[A]]. Sub[F[A]] is a Traversable[Applicative], given that F is an Applicative. Traversable.dist must be called to convert it to F[Sub[A]], which is the output type of traverse, i.e. an Applicative[Traverse].

But dist calls traverse, which walks the iteration again. Thus traverse combines Functor.map and dist into a single walk of the iteration.

Examples

Count a list of integers and map to a list of strings.

val state : State[Int,List[String]] = List( 1, 2, 3 ).traverse[State[Int,_],String]( i -> State[Int,String]( x -> (x+1,i.toString) ) ) state.init( 0 )

The result is a tuple of type : [Int, List[String]] with a value of (3, List( '1', '2', '3' )).

A State[Int,List[String]] is an Applicative[List[String]]. A List( 1, 2, 3 ) is a Traversable[Int]. So the type : T -> F[A] has the type

: Int
      ->

State[Int,String].

Details

In the above example, the State[Int,String] becomes a State[Int,List[String]] in step #4 of the iteration implementation algorithm for traverse:

Instance of Sub[A] is created and lifted to an Applicative of type F[Sub[A]] by calling Applicative.lift.

The instance of Sub[A] might be created by calling Sub.identity[A], if the Sub is also an IdentityLift. Or call F.lift( Sub.lift[A] ) if Sub is an Applicative, then skip step #2.
An accumulation function of type : Sub[A] A -> Sub[A] (which implicitly also has an alternative partial application type : Sub[A] -> (A -> Sub[A])) is input to F[Sub[A]].map, thus returning a value of type F[A -> Sub[A]].

This accumulation function might be the method Sub.append, if the Sub is also a MonoidLifted.
The next T (in the Traversable instance) is input to the function of type : T -> F[A].
The output F[A -> Sub[A]] of step #2 (if it is not None) is input to the apply method of the output F[A] of step #3, thus returning a value of type F[Sub[A]].
The output F[Sub[A]] of step #4, is then used in step #2.

In the above example, the function of type : A -> Sub[A] in step #4 is not called until state.init( 0 ) is called, because the State[Int,String].bind method (which is called by the apply method of step #4), assigns a closure on its input to the init field of the return value of type State[Int,List[String]].

Thus the accumulation doesn't build the List[String] until after the entire interation has completed. The 2-tuples of [Int,String] stored in the nested closures during iteration, are discarded when state.init( 0 ) is called.

Miscellaneous

Note that since Traversable.traverse is a method then it implicitly inputs this, and so when used as a function, it has the type : Sub[T]

(T
      -> F[A]) -> F[Sub[A]]

.

Theory

The Haskell example in the research paper that introduced Applicative:

Idiomatic traversal, The Essence of the Iterator Pattern,
Gibbons & Oliveira, sec3.4 on pg 8
Traversing data structures, Applicative programming with effects,
McBride & Paterson, sec3 on pg 6

is as follows, but note accum is f and identity is [].

traverseList : Applicative m => (() -> c) -> (b -> c) -> (c -> b -> c) -> (a -> m b) -> [a] -> m c traverseList identity accum map [] = pure identity traverseList identity accum map (head:[]) = pure (head:[]) traverseList identity accum map (head:tail) = (pure accum) <*> (traverse identity lift accum map tail) <*> (map head)

In Copute it has a similar three cases structure, where traversable (which is a list in the Haskell example) is generalized to Listable:

traverse = identity accum map { this | Empty -> F.lift(identity) | Headable(_, Empty) -> F.lift(this) // F.lift(accum) <- traverse(identity, accum, map, tail) <- map(head) | Headable(head, tail) -> traverse(identity, accum, map, tail).apply(map(head).apply(F.lift(accum))) } or accum <-- traverse(identity, accum, map, tail) <- map(head)

Note that from the following citation, accumulate has been generalized to Foldable.fold, concat is Foldable.flatten, and flatten is Foldable.convert.

Monoids are phantom Applicative functors,
Applicative programming with effects, McBride & Paterson,
sec4 on pg 7

Mixins

mixin Traverse[T] : Traversable[T], Listable[T],
      RevMonoidLifted[T]

      {

         traverse[F,A] = f

         {

            val recurse : F[Sub[A]] Listable[T]
      -> F[Sub[A]]

         @= prev list

            {

               list

               |
      Empty                  






      -> prev

               | Headable(head,
      tail)    -> recurse((t -> t.prepend) <--
      prev <- f(head), tail) // (Sub[A] -> (A -> Sub[A]))
      <-- F[Sub[A]] <- F[A]

            }

            recurse(

F.lift(Sub.

identity[A]),






      this).reverse // concise alternative is not tail-recursive,
      (prepend <-- tail.traverse(f) <- f(head)).reverse

         }



           traverse[F,A] = f

           {

              val recurse : F[Sub[A]]
        Listable[T] -> F[Sub[A]]

               @= prev
        list

              {

                 list

                 |
        Empty                  






        -> prev

                 |
        Headable(head, tail)

                   {

                     






          f(head)

                     






          | None   -> prev

                     






          | next   -> recurse((t -> t.prepend) <--
          prev <- next, tail)

                   }

       }

              recurse(F.lift(Sub.identity[A]),






        this).reverse

           }

      }

Given a Traversable, Listable, RevMonoidLifted, default implementation of:

Traversable.traverse

See traverse f (x : xs) = [[ (:) (f x) (traverse f xs) ]] in Section 3 Traversing data structures, Applicative programming with effects, McBride and Paterson.

x is head

xs is tail

(f x) has type F[A]

(traverse f xs) has type F[Sub[A]]

(:) is MonoidLifted.append which has type Sub[A] -> A -> Sub[A]

[[ ]] inside the brackets implies F.lift(append) and F.apply between each operand as explained on page 4

`x`	is head
`xs`	is tail
`(f x)`	has type `F[A]`
`(traverse f xs)`	has type `F[Sub[A]]`
`(:)`	is `MonoidLifted.append` which has type `Sub[A] -> A -> Sub[A]`
`[[ ]]`	inside the brackets implies `F.lift(append)` and `F.apply` between each operand as explained on page 4