Working character by character in Haskell

Tom Pledger
Fri, 19 Oct 2001 09:46:41 +1300

Andre W B Furtado writes:
 | copyFile :: String -> String -> IO String
 | copyFile [] s = return (reverse s)
 | copyFile (a:as) s = copyFile as ( (doSomeStuffWith a):s)
 | For example, suppose function doSomeStuffWith returns its own
 | parameter.  Using a 1.5MB file in this case, the Haskell program
 | ends in almost 5 seconds, while the C program ends in less than 0.5
 | seconds... Is my Haskell program too bad implemented? (I'm using
 | GHC 4.08-1 under a Windows 98 platform.)

You've used an accumulating parameter (s) and then reversed it once
you reach the end of the input.  The time cost for this is still O(n)
where n is the length of the input, but the space cost is O(n) in your
Haskell program and O(1) in your C program, so perhaps the Haskell
version's having to spend time enlarging its heap?

Here's an O(n) time, O(1) space version of copyFile:

    copyFile = return . map doSomeStuffWith