Scala Cats或Scalaz类型类scanLeft之类

Question

我想知道在Cats或Scalaz中是否有一个typeclass，它提供了这样的运算符：

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

或者，如果存在这样的算子的某种数学定义（类似于Monad的bind/flatMap）。

这个typeclass的想法是将二进制函数应用于类型构造函数并获取相同类型的构造函数，但使用不同的类型参数（二进制函数返回的相同类型）。

我认为类似于Scala标准库集合的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的scanLeft用于矢量和列表（但不是选项！），但需要相当多的类型类！不幸的是，stdlib scanLeft会预先设置初始元素，因此结果集合将始终是一个大于原始元素的元素，并且没有单个类型类提供任何类似的操作。

如果你没有预先加上zero就好了，你在G[_]上所需要的就是Traverse，这不是一半坏。如果你不是，你可能最好使用子类型进行泛化

Answer 2

回答原来的问题，不，我不认为已经有这样的类型类。但是，您可以使用Foldable实现类似的功能。

使用猫：

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严格，以便我可以确定标准库一个没有被调用。