[Haskell-cafe] Reference for technique wanted

Gregory Collins greg at gregorycollins.net
Sun Oct 31 19:05:37 EDT 2010

"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:

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

Gregory Collins <greg at gregorycollins.net>

More information about the Haskell-Cafe mailing list