[Haskell-cafe] Using ShowS or Difference Lists

Ryan Ingram ryani.spam at gmail.com
Sat Feb 6 13:28:13 EST 2010

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

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.

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

More information about the Haskell-Cafe mailing list