Difference lists recap

In CTM, around page 145, the authors talk about a list implementation called Difference Lists. At the abstract level, a dlist is just a list. an ordered list, that has constant time for pushing elements on the front, and a way to iterate over its elements, one by one. It's made of Conses, and the last cdr points to nil.

The difference with normal lists is that it provides -- thanks to the way how Oz (and prolog) can unify unbound variables -- a way to append 2 lists in constant time. The same principle, when applied can lead to very efficient implementations of operations like flatten or reverse, and this leads to efficient ways to code other datastructures like Queues.

I could try to explain how they work, and how you can achieve this performance speedups, but It's definately better if I just link to a few links, and then you skim them and realize how smart and mind bending it is to start thinking declaratively. :)

According to Clocksin: "probably one of the most ingeinous programming techniques ever invented yet neglected by mainstream computer science".

•  Helpful texts and articles
• http://en.literateprograms.org/Quicksort_%28Oz%29
• Clause and effect chapter on difference lists. Page 59.
• http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html
• http://stackoverflow.com/questions/20169862/understanding-difference-lists-prolog
• Applications of declarative programming and knowledge managing. 17th edition . Page 2.
• Presentations
• https://www.cl.cam.ac.uk/teaching/0809/Prolog/Prolog08ML5R2.pdf
• http://www.cs.rpi.edu/academics/courses/fall07/proglang/handouts/PLP11.3E,Sections3.4.3-3.4.4.pdf
• http://www.idi.ntnu.no/emner/tdt4165/handouts/09-handouts.pdf
•  
• Dlists in haskell
• http://www.cs.tufts.edu/~nr/cs257/archive/john-hughes/lists.pdf
• http://logicaltypes.blogspot.com.es/2008/08/difference-lists-in-haskell.html
• http://logicaltypes.blogspot.com.es/2008/08/using-difference-lists.html
• https://archive.is/20140131124629/http://web.archive.org/web/20080918101635/comonad.com/reader/2008/a-sort-of-difference/ 
• https://github.com/spl/dlist
• Other lists
• http://www.kr.tuwien.ac.at/events/wlp06/T02-final.pdf
• https://github.com/spl/dlist