I am trying to get my head around making this requirement as efficient as possible, because it is part of a combinatorial problem solver, so every little bit helps in the grand scheme of things.
Lets say I have a list of elements, in this case called transitions.
val possibleTransitions : List[Transition] = List[...] //coming from somewhere
I want to perform an (somewhat expensive) computation on each transition, to obtain another object, in this case called a State.
The natural way for me to do it is using a for-comprehension or a map. The former for me is more convenient because I want to filter out a few irrelevant State objects, such as those which were already processed earlier.
val newStates = for {
transition <- possibleTransitions
state <- computeExpensiveOperation(transition)
if (confirmNewState(state))
} yield state
State contains a value, lets call it value(), which indicates some kind of attractiveness of that state. If the value() is very low (attractive) I want to discard the rest of the list and use that. Since possibleTransitions could be a very long list (thousands), ideally I avoid doing that computeExpensiveOperation if for example the first State object already has the value() I want.
On the other hand, if I don't find any item with an attractive value() I want to keep all of them and add them to another list.
val newPending = pending ++ newStates
I was trying to use a Stream for this, to avoid computing all the values before processing them. If I use find() and I don't find the required item then I won't be able to get the items in the stream (since its use-once).
The only thing I can see possible at the moment is to use possibleItems.toStream() in the for-comprehension and create another collection, iterating through each item one by one until either I find the item (and discard the collection) or no (and use the collection with all items).
Am I missing some smarter more efficient way to do this?
I would use lazy views and convert them to a stream to cache the intermediate result, then you can get the information you need:
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
}
}
As the stream is lazy it will only be computed until the first element is found in the line with val attractive. If there is no attractive element the complete stream will be computed and cached and None will be returned.
When computing the new pending elements we can just append this stream to pending. (By the way: pending should probably be a Queue)