[Haskell-cafe] How to construct a lazy list of eagerly-evaluated items?

[Daniel Fischer]

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.