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.

Picador

Leaves me wondering what the properties of the returned value are – what are the laws of this typeclass? I mean I know it for scan on collection-like types. But can we generalize this? – Alleyway

@Alleyway Yes, for sure we could generalize it. The returned value (G[_]) could be a Monad/Functor like.. the scan itself can be implemented in terms of flatMap/map with an state in the method maybe. My thinking is something similar to Elm's foldp. Sorry for the late response. – Picador

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

Neologize

Good answer, just a small improvement: Applicative + MonoidK = Alternative =] – Louvenialouver

Could you please also add the Traverse only solution? I've always felt that prepending the initial element is wrong. – Alleyway

@Alleyway remove : Applicative: MonoidK bit and zero.pure[G] <+> bit. The rest is unchanged – Neologize

Answer 2

Answering the original question, no, I don't think there is such a typeclass already. However, you can implement similar functionality with Foldable.

Using Cats:

import cats.data.NonEmptyList
import cats.Foldable

implicit class ScanLeftable[F[_], T](val ts: F[T]) extends AnyVal {
  def scanLeft2[U](zero: U)(f: (U, T) => U)
                  (implicit fo: Foldable[F]): NonEmptyList[U] = {
    Foldable[F].foldLeft(ts, NonEmptyList.of(zero)) { (lu, t) =>
      f(lu.head, t) :: lu
    }.reverse
  }
}

import cats.instances.list._
val z = List(5, 10).scanLeft2(0)((a, b) => a + b)
println(z == NonEmptyList.of(0, 5, 15)) //true

You might try to make it more generic in terms of the return type, or return a lazy structure like Iterator, though. However, I'm not sure how generic it could be without introducing a new typeclass.

EDIT: the method is scanLeft2 strictly so that I can be sure the standard library one isn't called.

Prance

This looks pretty much like the way to go, but it would be interesting to see an implementation that did return a F[U] not a NonEmptyList[U]. Might need to include something like the CanBuildFrom from the standard library. – Maitilde

As @JoeK says I want it returns F[U] instead of a concrete collection like NonEmptyList where F[U] could be a custom infinite collection like for example. – Picador