[Haskell-cafe] Using ShowS or Difference Lists

[Holger Siegel]

Am Samstag, den 06.02.2010, 10:28 -0800 schrieb Ryan Ingram:
> As other people have mentioned, you are duplicating library
> functionality.  But nobody has actually talked about the performance
> characteristics of your code.
> 
> Fortunately for you, the calls to (++) in your recursion are
> right-associative, so you don't have an asymptotic problem where your
> program gets slower and slower for large inputs; it should stay
> linear.
> 
> But you are wasting some work.  In particular, (concat (intersperse "
> " l)) produces a String, and then (++) duplicates all of the cons
> cells in that string as it rebuilds it so that the tail connects with
> the next string.

By applying rewrite rules from the standard libraries, GHC figures out
that (concat xs ++ ys) == (foldr (++) ys xs) for every xs, ys. So, the
rule

joinLines (l:ls) = (concat (intersperse " " l)) ++ ('\n':joinLines ls)

becomes

joinLines (l:ls) = foldr (++) ('\n':joinLines ls) (intersperse " " l)

However, the problem remains the same: For every line you have to
construct a list (intersperse " " l) that is discarded immediately. But
if you implement function intersperse as

intersperse _   []      = []
intersperse sep (h:xs)  = h : concatMap (\x -> [sep,x]) xs

then you can derive the following implementation by applying the rules
for list fusion:

joinLines :: [[String]] -> String 
joinLines [[]]        = ""
joinLines [h:xs]      = h ++ foldr (\x y -> ' ': x ++ y) "" xs
joinLines ([]:ls)     = '\n':jl ls
joinLines ((h:xs):ls)
  = h ++ foldr (\x y -> ' ': x ++ y)  ('\n' : joinLines ls) xs

This version takes 10 seconds where the original version as well as the
idiomatic (unlines . map unwords) takes 15 seconds. Unfortunately, you
have to do that optimisation by hand; GHC doesn't figure it out by
itself.

> 
> So there is a potential benefit to using a difference list, albeit
> only by around a 2x factor.
> 
>   -- ryan
> 
> On Sat, Feb 6, 2010 at 4:42 AM, Mark Spezzano
> <mark.spezzano at chariot.net.au> wrote:
> > Hi,
> >
> > Just wondering whether I can use ShowS or tupling or Difference Lists to speed up the following code?
> >
> > It's basic text processing. It takes in a list of Lines where each Line is a list of Words and intersperses " " between them then concatenates them into a longer String. Note that there is a recursive call and the ++ operator.
> >
> > Thanks
> >
> > Mark
> >
> >
> > -- Function: joinLines
> > -- Joins the Words within Lines together with whitespace and newline characters
> > -- Argument: Lines to pad with whitespace and newlines
> > -- Evaluate: The processed and concatenated String
> > joinLines :: [Line] -> String
> > joinLines (l:[]) = concat (intersperse " " l)
> > joinLines (l:ls) = (concat (intersperse " " l)) ++ ('\n':joinLines ls)