返回由Zipper中的谓词过滤的流

Question

我已经编写了使用zipper +comonad查找第一个equilibrium index的代码：

import scalaz._
import Scalaz._

val in = NonEmptyList(-7, 1, 5, 2, -4, 3, 0)
in.toZipper
  .cobind { z => z.lefts.sum == z.rights.sum }
  .findNext(identity)
  .map(_.index)

// returns Some(3)
// I would like to return Some(3, 6) or even a scalaz stream?

我如何调整它以返回所有的平衡指数，而不是简单的第一个？

Answer 1

我想出了这个：

in.toZipper
  .cobind { z => z.lefts.sum == z.rights.sum }
  .toStream
  .zipWithIndex
  .filter(_._1)
  .map(_._2)

但我认为它的性能不是很好(由于子列表的反复求和)

Answer 2

我不能为您的scalaz解决方案提供帮助，但找到平衡指数的更简单的解决方案可能是：

def equilibriaIndices(numbers: List[Int]): List[Int] = {
  // sum numbers left side, sum numbers right side, indices equilibiria 
  val startAcc = (0, numbers.sum, List.empty[Int])
  val (_, _, equilibria) = numbers.zipWithIndex.foldLeft(startAcc) { 
    case ((sumLeft, sumRight, indices), (x, index)) => 
      val newIndices = if (sumLeft == sumRight - x) index :: indices else indices
      (sumLeft + x, sumRight - x, newIndices)
  }
  equilibria.reverse
}

这将为您提供：

scala> equilibriaIndices(List(-7, 1, 5, 2, -4, 3, 0))
res5: List[Int] = List(3, 6)

Answer 3

我认为用Zipper和cobind编写O(n)解决方案是不可能的。然而，很容易提出一个没有Zipper的解决方案(但仍然可以正常工作)：

val in = NonEmptyList(-7, 1, 5, 2, -4, 3, 0).list

val total = in.sum

in
  .scan(0)(_ + _)
  .zip(in)
  .map { case (leftSum, focus) => leftSum == total - leftSum - focus }
  .zipWithIndex
  .filter(_._1)
  .map(_._2)