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?

  • 1
    $\begingroup$ At first I was confused by “functional programming languages (as opposed to functional programming languages)”, but did you mean to write “(as opposed to logic programming languages)”? $\endgroup$ Commented Oct 24, 2010 at 4:10
  • $\begingroup$ Oh oops - yep, that's what I meant, it's fixed now. $\endgroup$ Commented Oct 24, 2010 at 4:14
  • $\begingroup$ The second question seems more appropriate on Stack Overflow to me but, now that you have asked it here, it may be better to wait to see if someone can answer here. Personally I cannot find any reason to doubt the claimed bounds from reading the source code, but I have not followed your reasoning to doubt them, and also I may be missing something. $\endgroup$ Commented Oct 24, 2010 at 4:31

2 Answers 2


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.

  • $\begingroup$ So what you're getting from laziness is just that asking for the tail of a list twice won't do the expensive operation twice, which is nice. $\endgroup$ Commented Oct 24, 2010 at 16:12
  • $\begingroup$ @Rob, I don't understand what you mean by that. $\endgroup$
    – jbapple
    Commented Oct 24, 2010 at 16:43
  • $\begingroup$ I think the point I was trying to make (badly) there is illustrated by this example: I have an extraordinarily long difference list "xs" that I made by repeatedly "snoc"ing things on to the original list. The first time I call "head xs" I expect that will take O(n) time to do deferred computation; however, because that computation should get memoized, the second call to "head xs" (for the same "xs") should take O(1) time. $\endgroup$ Commented Oct 24, 2010 at 17:53
  • 1
    $\begingroup$ Well, I agree with that, but the laziness I referenced in my answer was about fromList, which is not used in snoc or head. So, as, pedantic as it is, I was confused by the "what" in your statement "what you're getting from laziness". I'd say your example and mine are two things you're getting from laziness. $\endgroup$
    – jbapple
    Commented Oct 24, 2010 at 18:30
  • $\begingroup$ Ok - and that clarification helps me understand your earlier point better, as well. $\endgroup$ Commented Oct 24, 2010 at 19:07

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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.