On Sunday 23 May 2010 01:10:54, Vladimir Ch. wrote:
I'm using Project Euler to learn Haskell. In particular, I'm writing a program for Problem 18: <snip>
The program works, but consumes obscene amount of memory.
Not if it's compiled. Even interpreted I wouldn't call it obscene, though it is rather bad.
I suspect that it's because of lazy evaluation of items in the list we're constructing (and also using during construction).
Not really. Your problem is that you calculate maxPaths vals over and over again in where mpath i val = val + maximum [(maxPaths vals) !! pi| pi <- prev i] ; the value isn't shared (it is, if compiled with optimisations). If you share the list by giving it a name, your programme becomes much faster (interpreted or compiled without optimisations; with -O, it's below measuring accuracy anyway) and needs only a little memory: maxPaths vals@(v:vs) = mps where mps = v : zipWith mpath [1 .. ] vs mpath i val = val + maximum [mps !! pi| pi <- prev i]
How can I force eager evaluation of items, put into the list?
That's a little tricky. Fortunately, it's not necessary.
Any other comments and suggestions are also very welcome.
You can get rid of the index calculations and the list indexing if you work on the list of rows (i.e., make triangle18 :: [[Int]]). IMO, the code will be easier to follow then, too.
I know index-based item lookup in a list is not efficient, but I'll take care of this later (I don't know much about arrays yet). For now, I'm more concerned with the memory usage.