延迟计算列表中的项目，直到找到所需的元素

Question

我正在努力使这个需求尽可能高效，因为它是组合问题解决器的一部分，所以每一点都有助于宏伟的计划。

假设我有一个元素列表，在本例中称为过渡。

val possibleTransitions : List[Transition] = List[...] //coming from somewhere

我想对每个转换执行(有点昂贵的(计算，以获得另一个对象，在这种情况下称为State。

对我来说，这样做的自然方法是使用for-comprehension或map。前者对我来说更方便，因为我想过滤掉一些不相关的State对象，例如之前已经处理过的对象。

val newStates = for {
     transition <- possibleTransitions
     state <- computeExpensiveOperation(transition)
     if (confirmNewState(state))
} yield state

State包含一个值，我们称之为value()，它表示该状态的某种吸引力。如果value()非常低(有吸引力(，我想丢弃列表的其余部分并使用它。由于possibleTransitions可能是一个非常长的列表(数千个(，因此理想情况下，如果第一个State对象已经具有我想要的value()，则computeExpensiveOperation避免这样做。

另一方面，如果我找不到任何具有吸引力value()的项目，我想保留所有这些并将它们添加到另一个列表中。

val newPending = pending ++ newStates

我试图为此使用Stream，以避免在处理它们之前计算所有值。如果我使用 find() 并且找不到所需的项目，那么我将无法在流中获取项目(因为它使用了一次(。

目前我唯一能看到的就是在for-comprehension中使用possibleItems.toStream()并创建另一个集合，逐个迭代每个项目，直到我找到该项目(并丢弃集合(或没有(并将集合与所有项目一起使用(。

我是否缺少一些更聪明、更有效的方法？

Answer 1

我会使用惰性视图并将它们转换为流来缓存中间结果，然后您可以获得所需的信息：

val newStates = for {
     transition <- possibleTransitions.view
     state <- computeExpensiveOperation(transition)
     if (confirmNewState(state))
} yield state
val newStatesStream = newStates.toStream // cache results
val attractive = newStatesStream.find(isAttractive(_))
attractive match {
  case Some(a) => // do whatever
  case None => {
    val newPending = pending ++ newStatesSteam
  }
}

由于流是惰性的，因此只有在与 val attractive 的行中找到第一个元素之前才会计算它。如果没有吸引人的元素，则将计算和缓存完整的流，并返回 None。

在计算新的待处理元素时，我们可以将此流附加到挂起。(顺便说一下：挂起可能应该是一个队列(