Scala Cats or Scalaz typeclass scanLeft like

Question

I am wondering if there is a typeclass in Cats or Scalaz which offers an operator like this:

def scan[G[_],A,B](zero: B)(g: G[A],f: (A,B) => B):G[B]

Or if there exists some mathematical definition for such operator (something like Monad for bind/flatMap).

The idea of this typeclass would be apply a binary function to a type constructor and obtain back the same type constructor but with a different type parameter (the same type that binary function returns).

I think would be similar to scanLeft of Scala Standard Library collections.

Answer 1

One of possible implementation is to traverse with a State:

import cats._, data._, implicits._

def scan[G[_]: Traverse: Applicative: MonoidK, A, B](list: G[A], zero: B, f: (B, A) => B): G[B] = {
  def generate(a: A): State[B, B] =
    for {
      prev <- State.get[B]
      next =  f(prev, a)
      _    <- State.set(next)
    } yield next

  zero.pure[G] <+> list.traverse(generate).runA(zero).value
}

This works like scanLeft from stdlib for Vectors and Lists (but not options!), but requires quite a lot of typeclasses! Unfortunately, stdlib scanLeft prepends the initial element, so the result collection will always be one element larger than the original one and no single typeclass provides any similar operation.

If you are fine with not prepending zero, all you need on G[_] is Traverse and this is not half-bad. If you're not, you're probably better off generalizing using subtypes