在函数式编程中是否存在"折叠与中断"或"与累加器一起查找"的概念？

Question

标题说明了一切,真的; 迭代集合同时保持循环之间的状态和基于终止条件的完成迭代以及简单地耗尽元素可能是在命令式编程中完成任何事情的最常见模式.在我看来,像但它的东西功能gentleprogrammers同意不谈,至少我从来没有遇到过的成语,或一个半标化的名称,如用map,fold,reduce等.

我经常在scala中使用followinig代码:

implicit class FoldWhile[T](private val items :Iterable[T]) extends AnyVal {
    def foldWhile[A](start :A)(until :A=>Boolean)(op :(A, T)=>A) :A = {
        if (until(start)) start
        else {
            var accumulator = start
            items.find{ e => accumulator = op(accumulator, e); until(accumulator) }
            accumulator
        }

    }

}

但它很难看.每当我尝试一种更具声明性的方法时,我会使用更长,几乎肯定更慢的代码,类似于:

Iterator.iterate((start, items.iterator)){
    case (acc, i) if until(acc) => (acc, i)
    case (acc, i) if i.hasNext => (op(acc, i.next()), i)
    case x => x
}.dropWhile {
    case (acc, i) => !until(acc) && i.hasNext
}.next()._1

(一个更具功能性的变体将使用Lists或Streams,但迭代器的开销可能比转换items为a要小Stream,因为后者的默认实现使用下面的迭代器).

我的问题是:

1)这个概念在函数式编程中是否有名称,如果是,那么与其实现相关的模式是什么？

2)在scala中实现它的最佳方法(即简洁,通用,懒惰和最少开销)是什么？

Answer 1

scala纯粹主义者对此不以为然,但您可以使用如下return语句:

 def foldWhile[A](zero: A)(until:A => Boolean)(op:  (A,T) => A): A = items.fold(zero) {
      case (a, b) if until(a) => return a
      case (a,b) => op(a, b)
}

或者,如果你是那些皱眉的人之一,并且想要一个没有脏命令性技巧的纯功能解决方案,你可以使用懒惰的东西,比如迭代器或流:

items
  .toStream // or .iterator - it doesn't really matter much in this case
  .scanLeft(zero)(op)
  .find(until)

Answer 2

执行此类操作的功能方式是通过Tail Recursion:

implicit class FoldWhile[T](val items: Iterable[T]) extends AnyVal {

  def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = {
    @tailrec def loop(acc: A, remaining: Iterable[T]): A =
      if (remaining.isEmpty || !until(acc)) acc else loop(op(acc, remaining.head), remaining.tail)

    loop(zero, items)
  }
}

使用递归,您可以在每个步骤决定是否要继续使用break和不使用任何开销,因为尾递归会从编译器转换为迭代.

此外,模式匹配通常用于分解序列.例如,如果你有一个,List你可以这样做:

implicit class FoldWhile[T](val items: List[T]) extends AnyVal {

  def foldWhile[A](zero: A)(until: A => Boolean)(op: (A, T) => A): A = {
    @tailrec def loop(acc: A, remaining: List[T]): A = remaining match {
      case Nil              => acc
      case _ if !until(acc) => acc
      case h :: t           => loop(op(acc, h), t)
    }

    loop(zero, items)
  }
}

如果您要注释的函数不是尾递归的,Scala会使用@ scala.annotation.tailrec注释来强制编译失败.我建议你尽可能多地使用它,因为它有助于避免错误并记录代码.

Answer 3

其功能名称是 Iteratee。

关于这一点有很多参考资料，但最好从设计结束的地方开始阅读管道教程，并且只有当您有兴趣从那里向后工作以了解它是如何来自早期终止的左折叠时。