On Thu, 3 Jan 2008, Isaac Dupree wrote: > Achim Schneider wrote: > > Achim Schneider <[EMAIL PROTECTED]> wrote: > > > >> [...] > > > > I'm trying to grok that > > > > [] = id > > ++ = . > > > > in the context of Hughes lists. > > they are also known as "difference lists", and also used at type String > in the Prelude as "ShowS", to help avoid quadratic behavior when making > complicated Strings.
Sometimes I believed that I understand this reason, but then again I do not understand. I see that left-associative (++) like in ((a0 ++ a1) ++ a2) ++ a3 would cause quadratic time. But (++) is right-associative and 'concat' is 'foldr'. They should not scan the leading lists more than once. Also http://en.wikipedia.org/wiki/Difference_list doesn't answer this question. Where exactly is the problem? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
