This seems like an example of list-chauvinism -- what Chris Okasaki calls a communal blind spot of the FP community in Breadth-First Numbering: Lessons from a Small Exercise in Algorithm Design -- http://www.eecs.usma.edu/webs/people/okasaki/icfp00.ps
Thanks for sharing; this was an interesting (and short!) read.
I would like to see other Haskeller's responses to this problem. .. How would you implement bfnum? (If you've already read the paper, what was your first answer?)
That paper is indeed a useful read, provided one does try to solve the puzzle as well as carefully check any imagined solutions. I happened on it when I was working on the first GHood prototype, so my struggles happen to be documented (together with the popular foldl vs foldl' strictness) in the GHood paper and online examples: http://community.haskell.org/~claus/GHood/ The observation tool and problem turned out to be well suited for each other: by observing both the input and the result tree, one can see how traversal of the result tree drives evaluation of the input tree (or not, if one gets the strictness wrong;-). You might find this useful when testing your solutions or trying to get an intuition about dynamic strictness. Claus