CODEWITHSUNDEEP
scalafunctional-programmingscalazscala-cats
salc2
salc2

Reputation: 577

Scala Cats or Scalaz typeclass scanLeft like

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.

Upvotes: 5

Views: 428

Answers (2)

Oleg Pyzhcov
Oleg Pyzhcov

Reputation: 7353

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

Upvotes: 7

Jakub Kozłowski
Jakub Kozłowski

Reputation: 493

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.

Upvotes: 2

Related Questions