Difference lists in functional programming
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.)