Scala Cats或Scalaz类型类scanLeft之类

Question

我想知道如果有一个typeclass在猫或Scalaz它提供了一个操作是这样的:

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

或者,如果存在这样的运算符的某种数学定义(类似于Monadfor bind/flatMap).

这样做的想法是typeclass将二进制函数应用于类型构造函数并获取相同类型的构造函数,但使用不同的类型参数(二进制函数返回的相同类型).

我认为与scanLeftScala标准库集合类似.

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
}

这类似于scanLeftstdlib for Vectors和Lists(但不是选项!),但需要相当多的类型类!不幸的是,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严格的，以便我可以确定没有调用标准库。