[Haskell-cafe] Difference lists and ShowS (Was: The
daniel.is.fischer at web.de
Thu Jan 3 10:04:14 EST 2008
Am Donnerstag, 3. Januar 2008 14:48 schrieb Henning Thielemann:
> 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?
Show a binary tree inorder?
L-T-R gives (show L) ++ (show T ++ (show R))
gives ((show LL) ++ (showLT ++ (show LR))) ++ (show T ++ (show R))
gives (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++
(show T ++ (show R))
If the tree is large, you end up with a pretty large left association for the
left subtree. True, there's lot of right association, too, but bad enough, I
More information about the Haskell-Cafe