[Haskell-cafe] Difference lists and ShowS (Was: The Worker/Wrapper
lemming at henning-thielemann.de
Thu Jan 3 08:48:58 EST 2008
On Thu, 3 Jan 2008, Isaac Dupree wrote:
> Achim Schneider wrote:
> > Achim Schneider <barsoap at web.de> 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.
doesn't answer this question. Where exactly is the problem?
More information about the Haskell-Cafe