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
> <[email protected]> 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)
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
