Scala Streams Performance

Question

A canonical example of the usefulness of recursive algebraic data types and the lazy evaluation is a game algorithm, e.g. as shown in the famous WhyFP paper by John Hughes (Comp. J., Vol. 32, No. 2, 1989).

Implementing it with Scala, and using lazily evaluated Stream[Tree[A]] for each subtree of a game leads to trait Tree[A] with a definition:

sealed trait Tree[A]
case class Branch[A](ts: Stream[Tree[A]]) extends Tree[A]
case class Leaf[A](a: A) extends Tree[A]

Now a lazily evaluated, possibly infinite, game can be presented as:

gameTree(b: Board): Tree[Board] = 
  if (b.isAtEndPos) Leaf(b) 
  else Branch(b.emptySlots.toStream.map((pos: Int) => gameTree(b addTic pos)))

and you can implement a pruning, scoring and parallelization strategy to the the actual algorithm, that is for example minimax which does the job, and evaluates the parts of the tree which are necessary:

def maximize(tree: Tree[Board]): Int = tree match {
  case Leaf(board) => board.score
  case Branch(subgames) => 
     subgames.map((tree: Tree[Board]) => minimize(tree)).max
} ...
def minimize // symmetrically 

However, the infinite stream introduces a significant performance penalty, and solving identical game tree using eager list (ts: List[Tree[A]]) is 25 times more efficient.

Is there any way to use Streams or lazy structures in Scala effectively in similar situations?

Edit: added some performance results, and actual code: In link is the lazy version.

Lazy version (scala 2.9.1): Time for gametree creation: 0.031s and for finding the solution 133.216s.

No conversions in the tree creation, i.e. mapping over sets in minimax Time for gametree creation: 4.791s and for finding the solution 6.088s.

Converting to list in the gameTree creation Time for gametree creation: 4.438s and for finding the solution 5.601s.

Answer 1

If you want to get a quick and rough idea of where the time goes, you can try to run:

JAVA_OPTS="-Xprof" scala TicTacToe

As stated in the comments, I for one cannot reproduce your experience.