Traverse

Формальное определение

Предположим, что есть два функтора F и G. Traversable позволяет менять местами "обертку" функторов между собой, т.е. реализует операции traverse = (F[A], A => G[B]) -> G[F[B]] и sequence = F[G[A]] -> G[F[A]].

Traversable включает в себя повторение элементов структуры данных в стиле map, но интерпретацию определенных функциональных приложений идиоматически.

С помощью traverse можно выразить и map, и foldRight, а также sequence, отображающий F[G[A]] в G[F[A]]. По этой причине Traverse иногда называют "обходными функторами". Traverse расширяет Functor и Foldable

Traversable должен удовлетворять следующим законам:

Обход Id эквивалентен Functor#map:

traverse[F, Id, A, B](fa, a => Id(f(a))).value == fa.map(f)

Два последовательно зависимых эффекта могут быть объединены в один, их композицию:

val optFb: G[F[B]] = traverse[F, G, A, B](fa, a => unit(f(a)))
val optListFc1: G[H[F[C]]] =
map[G, F[B], H[F[C]]](optFb, fb => traverse[F, H, B, C](fb, b => unit(g(b))))
val optListFc2: G[H[F[C]]] =
traverse[F, [X] =>> G[H[X]], A, C](fa, a => map[G, B, H[C]](unit(f(a)), b => unit(g(b))))
optListFc1 == optListFc2

Обход с помощью функции unit аналогичен прямому применению функции unit:
```
traverse[F, G, A, A](fa, a => unit(a)) == unit[G, F[A]](fa)
```

Два независимых эффекта могут быть объединены в один эффект, их произведение

type GH[A] = (G[A], H[A])
val t1: GH[F[B]] = (traverse[F, G, A, B](fa, a => unit(f(a))), traverse[F, H, A, B](fa, a => unit(f(a))))
val t2: GH[F[B]] = traverse[F, GH, A, B](fa, a => (unit(f(a)), unit(f(a))))
t1 == t2

Определение в виде кода на Scala

trait Traverse[F[_]] extends Functor[F], Foldable[F]:
  self =>

  extension [A](fa: F[A])
    def traverse[G[_]: Applicative, B](f: A => G[B]): G[F[B]]

    override def map[B](f: A => B): F[B] = traverse(a => Id(f(a))).value

    override def foldRight[B](init: B)(f: (A, B) => B): B =
      traverse(a => State[B, A]((b: B) => (f(a, b), a))).run(init)._1

  def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
    fga.traverse(ga => ga)

Примеры

"Обертка"

case class Id[A](value: A)

given Traverse[Id] with
  extension [A](fa: Id[A])
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[Id[B]] =
      f(fa.value).map(b => Id(b))

Кортеж от двух и более элементов

given Traverse[[X] =>> (X, X)] with
  extension [A](fa: (A, A))
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[(B, B)] =
      val g = summon[Applicative[G]]
      val func: G[B => B => (B, B)] = g.unit(b1 => b2 => (b1, b2))
      g.apply(g.apply(func)(f(fa._1)))(f(fa._2))

given Traverse[[X] =>> (X, X, X)] with
  extension [A](fa: (A, A, A))
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[(B, B, B)] =
      val g = summon[Applicative[G]]
      val func: G[B => B => B => (B, B, B)] = g.unit(b1 => b2 => b3 => (b1, b2, b3))
      g.apply(g.apply(g.apply(func)(f(fa._1)))(f(fa._2)))(f(fa._3))

Option

given Traverse[Option] with
  extension [A](fa: Option[A])
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[Option[B]] =
      fa match
        case Some(a) => f(a).map(Some(_))
        case None    => summon[Applicative[G]].unit(None)

Последовательность

given Traverse[List] with
  extension [A](fa: List[A])
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[List[B]] =
      val g = summon[Applicative[G]]
      fa.foldRight(g.unit(List[B]()))((a, acc) => f(a).map2(acc)(_ :: _))

Дерево

В области видимости должны быть доступны idApplicative and listTraverse

case class Tree[+A](head: A, tail: List[Tree[A]])

given Traverse[Tree] with
  extension [A](ta: Tree[A])
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[Tree[B]] =
      f(ta.head).map2(ta.tail.traverse(a => a.traverse(f)))(Tree(_, _))

val tree = Tree(0, List(Tree(1, List(Tree(2, Nil)))))
tree.traverse(a => Id(a + 1))
// val res0: Id[Tree[Int]] = Id(Tree(1,List(Tree(2,List(Tree(3,List()))))))

Map

given mapTraverse[K]: Traverse[[X] =>> Map[K, X]] with
  extension [A](m: Map[K, A])
    override def traverse[G[_]: Applicative, B](f: A => G[B]): G[Map[K, B]] =
      m.foldLeft(summon[Applicative[G]].unit(Map.empty[K, B])) { case (acc, (k, a)) =>
        acc.map2(f(a))((m, b) => m + (k -> b))
      }

Реализация

Реализация в Cats

import scala.concurrent.*
import scala.concurrent.duration.*
import scala.concurrent.ExecutionContext.Implicits.global

val hostnames = List(
  "alpha.example.com",
  "beta.example.com",
  "gamma.demo.com"
)

def getUptime(hostname: String): Future[Int] =
  Future(hostname.length * 60)

val allUptimes: Future[List[Int]] =
  Future.traverse(hostnames)(getUptime)

Await.result(allUptimes, 1.second)  // List(1020, 960, 840)

Реализация в ScalaZ

import scalaz.*
import Scalaz.*

List(1, 2, 3) traverse { x => (x > 0) option (x + 1) }  // Some(List(2, 3, 4))
List(1.some, 2.some).sequence                           // Some(List(1, 2))
1.success[String].leaf.sequenceU map {_.drawTree}       // Success(1)

Ссылки: