My Functional Lists Design Problem: Continuations vs Traversal Algorithms
A non-trivial issue with the functional lists library I blogged about earlier is partial list traversal. Many common algorithms (such as get the n-th item) are guaranteed to terminate even with infinite lists. This is a flaw in the one ForEach method design I used. The ForEach is guaranteed to traverse the whole list. Not good.
I have found a workaround though, the addition of a CountWhile method. This method takes a predicate and will terminate abruptly when the predicate is no longer true. Alternatively I could have made the accessor passed to ForEach return a boolean value indicating whether to continue or not, or I could have scrapped the whole design and went with continuations (i.e. the yield statement).
The problem with having the ForEach return a boolean, is that it would require all iteration algorithms to have an extra check, whether or not it was needed. I’m not crazy about that, even if the C# compiler was theroetically smart enough to deal with it.
The problem with yield is that continuations can not be optimized as much as passing functions to iteration methods. This is because when calling an iteration method a smart compiler can inline the code. This is easy to force in C++ if we pass functions as template arguments. Â
A continuation however is a more flexible construct and can’t be optimized as easily. Of course in theory a really super-smart compiler could identify the usage pattern of a continuation as being the same as passing a function to an iteration algorithm. Unfortunately the C# compiler is years away from this technology.