在列表中获取元素直到Scala中的限制的功能方式

Question

该方法的目的是在列表中获取元素,直到达到限制.

例如

我想出了两个不同的实现

def take(l: List[Int], limit: Int): List[Int] = {
  var sum = 0
  l.takeWhile { e =>
    sum += e
    sum <= limit
  }
}

它很简单,但使用了可变状态.

def take(l: List[Int], limit: Int): List[Int] = {
  val summed = l.toStream.scanLeft(0) { case (e, sum) => sum + e }
  l.take(summed.indexWhere(_ > limit) - 1)
}

它看起来更干净,但它更冗长,也许内存效率更低,因为需要一个流.

有没有更好的办法 ？

Answer 1

你也可以在一次折叠中做到这一点：

  def take(l: List[Int], limit: Int): List[Int] =
    l.fold((List.empty[Int], 0)) { case ((res, acc), next) =>
      if (acc + next > limit)
        (res, limit)
      else
        (next :: res, next + acc)
    }

因为标准列表不是惰性的，折叠也不是，这将始终遍历整个列表。一种替代方法是使用猫来iteratorFoldM代替达到限制后短路的实现。

您还可以使用尾递归直接编写短路折叠，沿着这些路线：

def take(l: List[Int], limit: Int): List[Int] = {
  @annotation.tailrec
  def take0(list: List[Int], accList: List[Int], accSum: Int) : List[Int] =
    list match {
      case h :: t if accSum + h < limit =>  
        take0(t, h :: accList, h + accSum)
      case _ => accList
    }
  take0(l, Nil, 0).reverse
}

请注意，第二个解决方案可能更快，但也不太优雅，因为它需要额外的努力来证明实现终止，这在使用折叠时很明显。