Traverse

Traverse.scala

@typeclass trait Semigroup[A] {
  def combine(x: A, y: A): A
}

@typeclass trait Monoid[A] extends Semigroup[A] {
  def id: A
}

@typeclass trait Semigroupal[F[_]] {
  def product[A, B](ga: F[A], gb: F[B]): F[(A, B)]
}

@typeclass trait Monoidal[F[_]] extends Semigroupal[F] {
  def unit: F[Unit]
}

@typeclass trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}



def traverse[G[_]: Monoidal: Functor, A, B](l: List[A])(f: A => G[B]): G[List[B]] = {
  val seed: G[List[B]] = Monoidal[G].unit.map(_ => List.empty[B])
  l.foldRight(seed) { (a, glb) =>
    Monoidal[G].product(f(a), glb).map { case (head, tail) =>
      head :: tail
    }
  }
}

type Applicative[F[_]] = Functor[F] with Monoidal[F]

@typeclass trait Traverse[F[_]] extends Functor[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
  def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] = traverse(identity)
}