efficient list append/prepend through function composition

Question

Some months ago I read somewhere of an efficient approach for appending and prepending lists to other lists in O(1) by representing them with function compositions that, once evaluated, build in O(n) the resulting list.

Unfortunately I cannot remember the source of this article or (if existing) the name of this technique/approach. Do you have references about it, please?

Answer 1

The data structure is called a difference list (or DList for short). You can find a default implementation of it in a library available on Hackage.

As you mentioned, a full description can be gathered from a chapter in Real World Haskell on the subject.

Answer 2

You must be thinking of ShowS and friends from the Prelude. See here.