[Haskell-cafe] Weaving fun

[Derek Elkins]

Jan-Willem Maessen wrote:
> 
> On Apr 12, 2007, at 9:39 PM, Matthew Brecknell wrote:
> 
>> Jan-Willem Maessen:
>>> Interestingly, in this particular case what we obtain is isomorphic
>>> to constructing and reversing a list.
>>
>> Jan-Willem's observation also hints at some interesting performance
>> characteristics of difference lists. It's well known that difference
>> lists give O(1) concatenation, but I haven't seen much discussion of the
>> cost of conversion to ordinary lists.
> 
> Nice analysis, thanks to both of you.  I think a lot of this folklore 
> isn't widely understood, particularly the fact that the closures 
> constructed by difference lists are isomorphic to trees, with nodes 
> corresponding to append/compose and leaves corresponding to 
> empty/singleton.
> So you pay the cost for append each time you flatten---the difference 
> list trick is only a win if you flatten to an ordinary list once and/or 
> consume the entire list each time you flatten it.  I'd had an intuitive 
> notion of how this worked, but this spells it out nicely.
> 
> Of course, once you represent things like so:
> 
> data DiffList a = Segment [a]
>         | DiffList a :++ DiffList a
> 
> toList :: DiffList a -> [a]
> toList dl = toListApp dl []
> 
> toListApp :: DiffList a -> [a] -> [a]
> toListApp (Segment s) = (s++)
> toListApp (a:++b)     = toListApp a . toListApp b
> 
> You can start thinking about all sorts of other interesting questions, 
> beyond just transforming to a list and eta-abstracting toListApp.  The 
> next thing you know, you're writing a better pretty printer or otherwise 
> mucking about with the DiffList type itself to tailor it for your own 
> nefarious purposes.
> 
> -Jan
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

And the relationship between them is de-/re-functionalization, 
"Defunctionalization at Work" (http://www.brics.dk/RS/01/23/) has some 
interesting applications of ideas along the line of Jan's.