Archive for 2nd August 2010

Topless data

Functional programming abounds with recursively defined data types. We often draw these structured values as trees with the root at the top and the leaves at the bottom. Lazy functional programming allows values (structures) of these types to be “bottomless”, meaning we can descend forever. There are many examples of how supporting such values gives an enormous boost to modularity. (See, e.g., John Hughes’s classic paper Why Functional Programming Matters.) We usually refer to these values as “infinite”, but I’d like to suggest “bottomless” as a more specific alternative, and to point out a limitation that perhaps is not widely noticed.

Although we can descend infinitely in lazy functional programming, we can only ascend finitely. If I’m traversing a lazy list, there may be infinitely many elements on my right (yet to be visited) but only finitely many on my left (already visited). While traversing a tree, there may be infinite paths below but only a finite one above (leading to my current position).

In other words, our data is bottomless, but not topless. What would it be like to go beyond our usual merely uni-infinite data and program with bi-infinite data instead? With data that is both bottomless and topless?

Continue reading ‘Topless data’ »