```package scalaz

trait Traverse[T[_]] extends Functor[T] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], t: T[A]): F[T[B]]

import Scalaz._

override def fmap[A, B](k: T[A], f: A => B) = traverse[Identity, A, B](f(_), k)
}

object Traverse {
import Scalaz._

implicit def IdentityTraverse: Traverse[Identity] = new Traverse[Identity] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], t: Identity[A]) = f(t.value) ∘ (b => (b: B))
}

implicit def NonEmptyListTraverse: Traverse[NonEmptyList] = new Traverse[NonEmptyList] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: NonEmptyList[A]) = (as.list ↦ f) ∘ ((x: List[B]) => nel(x.head, x.tail))
}

implicit def TraversableTraverse[CC[X] <: collection.SeqLike[X, CC[X]] : CanBuildAnySelf]: Traverse[CC] = new Traverse[CC] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: CC[A]): F[CC[B]] = {
implicit val cbf = implicitly[CanBuildAnySelf[CC]].builder[B, B]
val ap: Apply[F] = implicitly[Apply[F]]

// Build up the result using streams to avoid potentially expensive prepend operation on other collections.
val flistbs: F[Stream[B]] = as.toStream.foldr(Stream.empty[B].η[F])((x, ys) => ap(f(x) ∘ ((a: B) => (b: Stream[B]) => a #:: b), ys))
flistbs ∘ {xs =>
val builder = cbf.apply()
for (x <- xs) builder += x
builder.result
}
}

}

implicit def Tuple1Traverse: Traverse[Tuple1] = new Traverse[Tuple1] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], t: Tuple1[A]) = f(t._1) ∘ (Tuple1(_: B))
}

implicit def Tuple2Traverse[X]: Traverse[({type λ[α]=(X, α)})#λ] = new Traverse[({type λ[α]=(X, α)})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: (X, A)): F[(X, B)] =
f(as._2) ∘ ((b: B) => (as._1, b))
}

implicit def Function0Traverse: Traverse[Function0] = new Traverse[Function0] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], t: () => A) = f(t.apply) ∘ ((b: B) => () => b)
}

implicit def OptionTraverse: Traverse[Option] = new Traverse[Option] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], ta: Option[A]): F[Option[B]] =
ta match {
case None => (none[B]) η
case Some(x) => f(x) ∘ (Some(_: B))
}
}

implicit def LazyOptionTraverse: Traverse[LazyOption] = new Traverse[LazyOption] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], ta: LazyOption[A]): F[LazyOption[B]] =
ta.fold(a => f(a) ∘ (LazyOption.some(_: B)), (LazyOption.none[B]) η)
}

import concurrent.Promise

implicit def PromiseTraverse: Traverse[Promise] = new Traverse[Promise] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], ta: Promise[A]): F[Promise[B]] =
f(ta.get) ∘ (promise(_: B)(ta.strategy))
}

implicit def ZipperTraverse: Traverse[Zipper] = new Traverse[Zipper] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], za: Zipper[A]): F[Zipper[B]] = {
val z = (zipper(_: Stream[B], _: B, _: Stream[B])).curried
val a = implicitly[Applicative[F]]
a.apply(a.apply(a.fmap(a.fmap(TraversableTraverse[Stream].traverse[F, A, B](f, za.lefts.reverse), (_: Stream[B]).reverse),
z), f(za.focus)), TraversableTraverse[Stream].traverse[F, A, B](f, za.rights))
}
}

implicit def ZipStreamTraverse: Traverse[ZipStream] = new Traverse[ZipStream] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], za: ZipStream[A]): F[ZipStream[B]] =
TraversableTraverse[Stream].traverse[F, A, B](f, za.value) ∘ ((_: Stream[B]) ʐ)
}

implicit def TreeTraverse: Traverse[Tree] = new Traverse[Tree] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], ta: Tree[A]): F[Tree[B]] = {
val trav = (t: Tree[A]) => traverse[F, A, B](f, t)
val cons = (x: B) => (xs: Stream[Tree[B]]) => node(x, xs)
val a = implicitly[Applicative[F]]
a.apply(a.fmap(f(ta.rootLabel), cons), TraversableTraverse[Stream].traverse[F, Tree[A], Tree[B]](trav, ta.subForest))
}
}

implicit def EitherLeftTraverse[X]: Traverse[({type λ[α]=Either.LeftProjection[α, X]})#λ] = new Traverse[({type λ[α]=Either.LeftProjection[α, X]})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: Either.LeftProjection[A, X]): F[Either.LeftProjection[B, X]] =
as.e match {
case Right(x) => (Right(x).left: Either.LeftProjection[B, X]) η
case Left(x) => f(x) ∘ (Left(_: B).left)
}
}

implicit def EitherRightTraverse[X]: Traverse[({type λ[α]=Either.RightProjection[X, α]})#λ] = new Traverse[({type λ[α]=Either.RightProjection[X, α]})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: Either.RightProjection[X, A]): F[Either.RightProjection[X, B]] =
as.e match {
case Left(x) => (Left(x).right: Either.RightProjection[X, B]) η
case Right(x) => f(x) ∘ (Right(_: B).right)
}
}

implicit def ValidationTraverse[X]: Traverse[({type λ[α]=Validation[X, α]})#λ] = new Traverse[({type λ[α]=Validation[X, α]})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: Validation[X, A]): F[Validation[X, B]] = as match {
case Success(x) => f(x) ∘ (Success(_: B))
case Failure(x) => (Failure(x): Validation[X, B]) η
}
}

implicit def ValidationFailureTraverse[X]: Traverse[({type λ[α]=FailProjection[α, X]})#λ] = new Traverse[({type λ[α]=FailProjection[α, X]})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: FailProjection[A, X]): F[FailProjection[B, X]] =
as.validation match {
case Success(x) => (Success(x).fail: FailProjection[B, X]) η
case Failure(x) => f(x) ∘ (Failure(_: B).fail)
}
}

import java.util.concurrent.Callable

implicit def CallableTraverse: Traverse[Callable] = new Traverse[Callable] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: Callable[A]): F[Callable[B]] = f(as.call) ∘ (b =>
new Callable[B] {
def call = b
})
}

import java.util.Map.Entry
import java.util.AbstractMap.SimpleImmutableEntry

implicit def MapEntryTraverse[X]: Traverse[({type λ[α]=Entry[X, α]})#λ] = new Traverse[({type λ[α]=Entry[X, α]})#λ] {
def traverse[F[_] : Applicative, A, B](f: A => F[B], as: Entry[X, A]): F[Entry[X, B]] = f(as.getValue) ∘ ((b: B) => new SimpleImmutableEntry(as.getKey, b))
}
}

```