[Haskell-beginners] what to do about excess memory usage

[James Jones]

I finally got serious about learning Haskell and have started by trying 
to write as efficient and clear a program to solve the Code Jam 2013 
"Fair and Square" problem as I can. (Since the qualifying round is long 
over, I have "cheated" some; I peeked at the analysis to see what I had 
missed when working on it by myself, and borrowed some very nice 
semilattice tree search code by Twan van Laarhoven and an integer square 
root routine.) You can see the result at http://pastebin.com/JuyaNLRp 
(apologies for what pastebin's Haskell source highlighting does when you 
have an identifier with an apostrophe).

The result now processes the test input with values up to a googol in 
about 0.2 seconds on my not particularly high-end computer. I'd say 
that's as good as I can do and go on to the next problem, but profiling 
turns up that

* it's spending 45% of its time garbage collecting. (ouch!)
* one function, pairSum, is consuming a lot of RAM--about two megabytes 
at the end.

It seems like a simple function. Here it is, along with most of the 
things it uses.

**powersOfTen = map (10 ^) [0..]
           halfN      = n `div` 2
           shell      = pair 0
           memoPair   = zipWith (+) powersOfTen
                                    (take halfN (reverse (take n 
powersOfTen)))
           pair i     = memoPair !! i
           pairSum xs = foldl' (+) shell (map pair xs)

(pair i gives the matching 1s in the top and bottom half of a palindrome 
that has only ones and zeroes; pairsum takes a list of positions of ones 
and generates the corresponding palindrome.) I suspect thunks are 
accumulating, but I don't know how to get rid of them.  I've tried bang 
patterns and $!, to no avail. I still haven't wrapped my brain around seq.

There are other things that should be improved about the code, but I 
think I can figure those out myself. I've leaned heavily on Chapter 25 
of Real World Haskell to get the code to this point, but it's not 
getting through to me how to apply its techniques here. Any suggestions 
or pointers would be greatly appreciated.