22 May
2010
22 May
'10
9:33 p.m.
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!