How to construct a lazy list of eagerly-evaluated items?
I'm using Project Euler to learn Haskell. In particular, I'm writing a program for Problem 18: http://projecteuler.net/index.php?section=problems&id=18. As a solution, I'm constructing a list, containing maximum sums of values on a path from top of the triangle to a given item. In this list, item value equals value of an item from an input list plus maximum of values of the "top neighbours", taken from the same list we're constructing. Here's the program: BEGIN CODE triangle18 = [75...etc - definition of the input triangle sqrti n = truncate (sqrt (fromIntegral n)) -- returns true if a number is an exact square isSquare n = n == r * r where r = sqrti n -- returns true if a number is a triangular numberx isTriangular n = isSquare (8 * n + 1) -- returns index of the top-right neighbour prevRight i = i - (sqrti (8 * i + 1) - 1) `div` 2 -- returns index of the top-left neighbour prevLeft i = prevRight i - 1 -- returns the list of top neighbours (at most 2) prev i | i == 0 = [] | isTriangular i = [prevRight i] | isTriangular (i + 1) = [prevLeft i] | otherwise = [prevLeft i, prevRight i] -- returns the list of 'path sums' for a given list of input numbers maxPaths vals@(v:vs) = v : zipWith mpath [1..] vs where mpath i val = val + maximum [(maxPaths vals) !! pi| pi <- prev i] result18 = maximum (maxPaths triangle18) END CODE The program works, but consumes obscene amount of memory. I suspect that it's because of lazy evaluation of items in the list we're constructing (and also using during construction). How can I force eager evaluation of items, put into the list? Any other comments and suggestions are also very welcome. 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.
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.
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]
Thank you - exactly the kind of answer I was looking for!
participants (2)
-
Daniel Fischer -
Vladimir Ch.