The question What's new in purely functional data structures since Okasaki?, and jbapple's epic answer, mentioned using difference lists in functional programming (as opposed to logic programming), which is something I've recently been interested in. This led me to find the difference list implementation for Haskell. I have two questions (forgive/correct me if I should make them two different questions on the StackExchange).
The simple question is, is anyone aware of academic consideration of difference lists in functional programming and/or implementations besides the one in the Haskell library? jbapple's answer didn't give a citation for difference lists (difference lists in logic programming exist in the lore and in a couple of sources which I have Around Here Somewhere (TM)). Before finding the Haskell implementation I wasn't aware that the idea had leaped from logic to functional programming. Granted, the Haskell difference lists are something of a natural use of higher-order functions and work quite differently from the ones in logic programming, but the interface is certainly similar.
The more interesting (and far fuzzier-headed) thing I wanted to ask about is whether the claimed asymptotic upper bound for the aforementioned Haskell difference list library seems correct/plausible. My confusion may be because I am missing something about obvious about complexity reasoning with laziness, but the claimed bounds only make sense to me if substitution over a large data structure (or closure formation, or variable lookup, or something) always takes constant time. Or is the "catch" simply that there's no bound on the running time for "head" and "tail" precisely because those operations may have to plow through an arbitrary pile of deferred computations/substitutions?