类Scala猫或Scalaz类型的scanLeft

Question

我想知道Cats或Scalaz中是否有一个typeclass，它提供了这样一个操作符：

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

或者，如果存在这样的运算符的数学定义(类似于Monad for bind/flatMap)。

此typeclass的思想是将二进制函数应用于类型构造函数，并获得相同类型的构造函数，但具有不同的类型参数(二进制函数返回的类型相同)。

我认为类似于Standard的scanLeft集合。

Answer 1

可能的实现之一是使用一个traverse实现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
}

这类似于stdlib为Vectors和List提供的scanLeft (但不是选项！)，但是需要相当多的类型！不幸的是，stdlib scanLeft在初始元素的前面加上了一个元素，因此结果集合总是比原始元素大一个，并且没有一个类型库提供类似的操作。

如果您不需要预置zero，那么您只需要在G[_]上使用Traverse，而这并不是半坏的。如果没有，则最好使用子类型进行泛化。

Answer 2

回答原来的问题，不，我认为还没有这样的典型。但是，您可以使用可折叠实现类似的功能。

使用猫：

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

但是，您可以尝试使它在返回类型方面更加通用，或者返回像Iterator这样的惰性结构。但是，如果不引入一个新的类型，我不知道它有多通用。

编辑:这个方法是严格的scanLeft2，这样我就可以确定标准库一个不会被调用。