I'm a recovering programmer who has been designing video games since the 1980s, doing things that seem baroquely hardcore in retrospect, like writing Super Nintendo games entirely in assembly language. These days I use whatever tools are the most fun and give me the biggest advantage.
james.hague @ gmail.com
Where are the comments?
Trapped! Inside a Recursive Data StructureFlat lists are simple. That's what list comprehensions are designed to work with, for example. Code for scanning or transforming a flat list can usually be tail recursive. Once data becomes deep, where elements of a list can contain other lists ad infinitum something changes. It's trivial to iterate over a deep list; any basic Scheme textbook covers this early on. You recurse down, down, down, counting up values, building lists, and then....trapped. You're way down inside a function, and all you really want to do is exit immediately or record some data that applies to the whole nested data structure and keep going, but you can't.
As an example, here's the standard "is X contained in a list?" function written in Erlang:
There are a couple of options here. One is to throw an exception. Another is to use continuation passing style. But there's a third approach which I think is cleaner: manage a stack yourself instead of using the function call stack. This keeps the function tail recursive, making it easy to exit or handle counters or accumulators across the whole deep data structure.
memberfor deep lists written with an explicit stack:
Would I really write
memberlike this? Probably not. But I've found more complex cases where this style is much less restrictive than writing a truly recursive function. One of the signs that this might be useful is if you're operating across a deep data structure as a whole. For example, counting the number of atoms in a deep list. Or taking a deep data structure and transforming into into one that's flat.