title: Type-safe difference lists
body: <p>A common idiom in Haskell, difference lists, is to represent a list <code>xs</code> as the value <code>(xs ++)</code>. Then <code>(.)</code> becomes "<code>(++)</code>" and <code>id</code> becomes "<code>[]</code>" (in fact this works for any monoid or category). Since we can compose functions in constant time, this gives us a nice way to efficiently build up lists by appending.</p>
  
  <p>Unfortunately the type <code>[a] -&gt; [a]</code> is way bigger than the type of functions of the form <code>(xs ++)</code> -- most functions on lists do something other than prepend to their argument.</p>
  
  <p>One approach around this (as used in <code>dlist</code>) is to make a special <code>DList</code> type with a smart constructor. Another approach (as used in <code>ShowS</code>) is to not enforce the constraint anywhere and hope for the best. But is there a nice way of keeping all the desired properties of difference lists while using a type that's exactly the right size?</p>