Wednesday, May 19, 2010

F# -- excessively lazy sequences and stateful visitors

Doing something a little bit complicated here: the functional equivalent of a visitor pattern, where I want to apply a few functions to a long and potentially expensive to traverse sequence of items (so ruling out a series of iterations over the visited nodes) --

BuildNodeSequence itself returns a nested sequence expression of the data to visit, and state is well, expected to be handled by mutable out-of-band means.

This works nicely, but is impure -- so let's try to fix that by having the visitor function update itself with the transient state we need to carry between (there will still be side-effects for output). The code becomes

where the Fix delegate type is a way of reifying an otherwise infinite type Node ->'a where 'a is also Node ->'a through

and have it build

Well, I run this and...

Nothing happens -- or at least apply gets called for every node to visit, but invoke never did; until I forced the evaluation of the visitors sequence by

So, what I finally ended up with is

where the inner iterable is evaluated eagerly, rather than being left to lazy IEnumerable expansion; and this then works.

Post a Comment