The bottom line is that
- in logic programming languages, building a list by working on a pair of arguments representing a segment of the list is the NORMAL way to build a list; it's as fast as it gets, and the list is inspectable during construction.
modulo usage patterns: e.g., mostly linear use.
- at least in SML, the (fn ys => xs @ ys) [Haskell: \ys -> xs ++ ys] approach is stunningly slow, so slow as to make even naive use of append more attractive for most uses of; it is not the normal way to build lists, and for good reason; you can do nothing with a list so represented except compose and apply.
Even in your SML code, the "boring old plain lists" seemed to be list_flatten, which uses difference lists in disguise, and won your little test, right? Using Haskell notation: flat (LEAF x) ys = x : ys flat (FORK(a,b)) ys = flat a (flat b ys) --> flat (LEAF x) = \ys->x : ys flat (FORK(a,b)) = \ys->flat a (flat b ys) --> flat (LEAF x) = (x :) flat (FORK(a,b)) = flat a . flat b As in Prolog, it is often better not to make the structure explicit, though I am slightly disappointed that GHC's optimizer doesn't give the same performance for the two versions (when summing a flattened strict tree in Haskell, I get roughly a factor of 2 between naive list append, explicit diff lists, as in the lower version of flat, and hidden diff lists, as in your list_flatten, the latter being fastest). Of course, one has to be careful about usage patterns and efficiency considerations. For instance, head and tail with Haskell diff lists are not O(n), as you mentioned, because of non-strictness. And building up lots of nested operations under a lambda means that many of those operations are not likely to be shared, but repeated every time the lambda is applied (such as converting back to plain lists), so one has to be careful about not doing that too often. etc.
The practical consequence of this is that calling both techniques by the same name is going to mislead people familiar with one kind of language when they use the other: logic programmers will wrongly expect dlists to be practically useful in functional languags, functional programmers will expect them to be impractical in logic programming languages.
I do tend to expect a little more insight from Haskellers, but perhaps you're right. Having a pre-canned library instead of writing out the near-trivial code patterns oneself, one might be surprised when expected miracles don't happen (diffarrays were one such case for me;-). I'd still call both patterns difference lists, because it can be useful to know about the connections, but if you could suggest text for the DList documentation that warns of the differences, and of performance pitfalls, I'm sure the package author would be happy to add such improvements. If we ever get per-package wikis for hackage, you could add such comments yourself. Claus