[Haskell-cafe] Difference lists and ShowS (Was: The Worker/Wrapper
lemming at henning-thielemann.de
Thu Jan 3 10:27:43 EST 2008
On Thu, 3 Jan 2008, Daniel Fischer wrote:
> Am Donnerstag, 3. Januar 2008 14:48 schrieb Henning Thielemann:
> > 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?
> 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
With difference lists I write
shows L . (shows T . shows R)
(shows LL . (showsLT . shows LR)) . (shows T . shows R)
((shows LLL . (shows LLT . shows LLR)) . (showsLT . shows LR)) . (shows T . shows R)
I still need to resolve three (.) until I get to the first character of
the result string, but for the subsequent characters I do not need to
resolve those dots. In the end, resolution of all (.) may need some time
but then concatenation is performed entirely right-associative. Seems to
be that this is the trick ...
More information about the Haskell-Cafe