[Haskell-cafe] Reference for technique wanted

[Gregory Collins]

"Richard O'Keefe" <ok at cs.otago.ac.nz> writes:

> There's a long-known technique in functional languages
> where
> 	[x1,...,xn]	=> \tail -> x1:...xn:tail
> 	xs ++ ys	=> f . g
> 	xs		=> f []
>
> A correspondent mentioned to me that he couldn't find a reference
> to the idea (which I gather he had independently rediscovered).
> I know I've read about it somewhere.  Can anyone provide a reference?

They're called difference lists:
http://hackage.haskell.org/packages/archive/dlist/latest/doc/html/Data-DList.html

They allow O(1) snoc and append. I use them all the time!

G
-- 
Gregory Collins <greg at gregorycollins.net>