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

<pre><code>datatype 'a join = Nil | Cons of 'a * 'a join | Join of 'a join * 'a join
</code></pre>

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

CC BY-SA 2.5
2010-10-24T10:25:42.550Z
2010-10-24T10:25:42.550Z
Neel Krishnaswami
<blockquote>
  <p>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?</p>
</blockquote>

<p>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.</p>

<p>The following defunctionalized version of some of the essential operations requires laziness for $O(1)$ <code>fromList</code>, but otherwise should be a straightforward way of understanding the complexity bounds claimed in <a href="http://hackage.haskell.org/packages/archive/dlist/0.5/doc/html/src/Data-DList.html#fromList" rel="noreferrer">the original</a>.</p>

<pre><code>{-# 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)
</code></pre>

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

CC BY-SA 4.0
2020-03-03T08:00:41.323Z
@RobSimmons if `head` goes through `toList` as the answer suggests, the advantage disappears and if we do another `snoc`, the next `head` / `tail` will work anew from the start. instead, combine `head+tail` into one operation `unCons` which will rotate the tree to the right as it percolates the leftmost node up. that becomes `head`, and the rest - `tail`, which is ready for further `snoc`ing *and* is good for the next `unCons` at the same time. the overall amortized cxty of `unCons` will likely be approx. O(1) per element. I suggest this [here](https://stackoverflow.com/a/43945275/849891).
Will Ness
CC BY-SA 4.0
2020-03-03T08:03:53.983Z
i.e. after the tree is fully rotated, we have `unCons (Compose (Cons a) t) = (a,t)` etc. we can rotate it because composition is associative, of course.
Will Ness
CC BY-SA 2.5
2010-10-24T16:12:11.420Z
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.
Rob Simmons
CC BY-SA 2.5
2010-10-24T16:43:19.970Z
@Rob, I don't understand what you mean by that.
jbapple
CC BY-SA 2.5
2010-10-24T17:53:42.283Z
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.
Rob Simmons
CC BY-SA 2.5
2010-10-24T18:30:16.717Z
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.
jbapple
CC BY-SA 2.5
2010-10-24T19:07:10.897Z
Ok - and that clarification helps me understand your earlier point better, as well.
Rob Simmons
CC BY-SA 2.5
2010-10-24T10:36:21.123Z
2010-10-24T21:30:32.053Z
2010-10-24T21:30:32.053Z
jbapple
<p>The question <a href="https://cstheory.stackexchange.com/questions/1539/whats-new-in-purely-functional-data-structures-since-okasaki">What's new in purely functional data structures since Okasaki?</a>, 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 <a href="http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist" rel="nofollow noreferrer">difference list</a> implementation for Haskell. I have two questions (forgive/correct me if I should make them two different questions on the StackExchange).</p>

<p>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.</p>

<p>The more interesting (and far fuzzier-headed) thing I wanted to ask about is whether the claimed asymptotic upper bound for the <a href="http://hackage.haskell.org/packages/archive/dlist/0.5/doc/html/Data-DList.html" rel="nofollow noreferrer">aforementioned Haskell difference list library</a> 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 <i>something</i>) 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?</p>

CC BY-SA 2.5
2010-10-24T04:10:48.063Z
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)”?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-24T04:14:27.427Z
Oh oops - yep, that's what I meant, it's fixed now.
Rob Simmons
CC BY-SA 2.5
2010-10-24T04:31:15.010Z
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.
Tsuyoshi Ito
<reference-request><ds.data-structures><pl.programming-languages><functional-programming><logic-programming>
Difference lists in functional programming
Rob Simmons
# Difference lists in functional programming

(Asked by: username_0 on 2010-10-24)

The question [What's new in purely functional data structures since Okasaki?](https://cstheory.stackexchange.com/questions/1539/whats-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](http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist) 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](http://hackage.haskell.org/packages/archive/dlist/0.5/doc/html/Data-DList.html) 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?

**Tags:** reference-request, ds.data-structures, pl.programming-languages, functional-programming, logic-programming
> **Comments:**
> **username_1**: 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)”?  
> **username_0**: Oh oops - yep, that's what I meant, it's fixed now.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2010-10-24. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: @Rob, I don't understand what you mean by that.  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: Ok - and that clarification helps me understand your earlier point better, as well.  
> **username_4**: @RobSimmons if `head` goes through `toList` as the answer suggests, the advantage disappears and if we do another `snoc`, the next `head` / `tail` will work anew from the start. instead, combine `head+tail` into one operation `unCons` which will rotate the tree to the right as it percolates the leftmost node up. that becomes `head`, and the rest - `tail`, which is ready for further `snoc`ing *and* is good for the next `unCons` at the same time. the overall amortized cxty of `unCons` will likely be approx. O(1) per element. I suggest this [here](https://stackoverflow.com/a/43945275/849891).  
> **username_4**: i.e. after the tree is fully rotated, we have `unCons (Compose (Cons a) t) = (a,t)` etc. we can rotate it because composition is associative, of course.  

---

### Answer by username_2 on 2010-10-24. Score: 12

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


---

