Difference lists in functional programming

Question

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?

Answer 1

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?

I think that's more or less correct. DLs only really have fast build operations, though, so the plowing is $\Theta(m)$, where $m$ is the number of operations used to build the DL.

The following defunctionalized version of some of the essential operations requires laziness for $O(1)$ fromList, but otherwise should be a straightforward way of understanding the complexity bounds claimed in the original.

{-# LANGUAGE NoMonomorphismRestriction #-}

data DL a = Id
          | Cons a
          | Compose (DL a) (DL a)

fromList [] = Id
fromList (x:xs) = Compose (Cons x) (fromList xs)

toList x = help x []
    where help Id r = r
          help (Cons a) r = a:r
          help (Compose f g) r = help f $ help g r

empty = Id

singleton = Cons

cons x = append (singleton x)

append = Compose

snoc xs x = append xs (singleton x)

The $\Theta(n)$ operations head and tail can be implemented the same way as they are in the [a] -> [a] version, using toList.

Answer 2

Yes, the bounds depend on the assumption that function composition takes constant time. Basically, if you have a join list:

datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join

It's obvious that concatenation is constant time, and that it's $O(n)$ to turn this into a cons-list. If you think about the usual representation of closures, you can see that this is basically the same pointer representation as the usual representation of datatypes. (Alternatively, you can view this type as a defunctionalized difference-list.)