Lazy Traverse Fold

LazyTraverseFold.scala

type M[_] is a monad

def f(as: List[A])(m: A => M[B](c0: C)(g: (C, B) => C)(implicit MM: Monad[M]): M[C] = {
 
  def go(c: C, ras: List[A]): M[C] = ras match {
    case Nil => MM.point(c)
    case head :: tail => m(head).flatMap(b => go(g(c, b), tail))
  }
  
  go(c0, as)
}
  
// pass C around as M[C]
def f(as: List[A])(m: A => M[B](mc0: M[C])(g: (C, B) => C)(implicit MM: Monad[M]): M[C] = {
 
  def go(mc: M[C], ras: List[A]): M[C] = ras match {
    case Nil => mc
    case head :: tail => m(head).flatMap(go(mc.map(c => g(c, b))))
  }
  
  go(mc0, as)
}

def f(as: List[A])(m: A => M[B](mc0: M[C])(g: (C, B) => C)(implicit MM: Monad[M]): M[C] = 
  as.foldLeft[M[C]](mc0){case (mc: M[C], a: A) => {
    for {
      b <- m(a)
      c <- mc
    } yield g(c, b)
  }}