Haskell method is too slow

Question

I wrote a function in Haskell which looks like this:

maxSumme :: [[Int]] -> Int
maxSumme [] = 0
maxSumme (x:l) = if subSumme x < maxSumme l then maxSumme l else subSumme x

subSumme :: [Int] -> Int
subSumme [] = 0             
subSumme (x:l) = x + subSumme(l)

-- function call
maxSumme [[7,2,4],[5,8,1],[7,9,2]] -- with 25 innerLists

I tested it but this method is very slowly. If I call it with a list of 25 innerLists with 3 items it takes up to a minute to calculate the maxSumme. That is not normal isn't it? I must have made a mistake but I can't find it. How can I optimize my method? Is there a faster way to do this?

EDIT: I think found the mistake. I'm convinced that it is the maxSumme l then maxSumme l. I loop throught the list to often each time and that takes so long. But actually I have no idea how to avoid that.

let lifting the maxSumme l reduces the time complexity from exponential to linear. CSE is not always ok in lazy languages, but it is in this case. — Philip JF
I'm new to Haskell. What do you mean with left lifting and CSE? It would be great if I can change it to a linear function — Cilenco
He means wrapping the code which repeat subSumme x in let ssx = subSumme x in ... (and replacing subSumme x with ssx). It's like defining a new variable, in some sort. Also the same goes for maxSumme l. CSE means "common subexpression elimination". If the compiler would have realized that those expressions are the same, it could have done what we just described and opmitized the hell out of the code, but for some reason it didn't (maybe it's not always ok as Philip suggests). — Guido
CSE can lead to more sharing and thus worsen asymptotic space efficency. GHC thus does less CSE than other agressive production quality compilers for this reason, although it could probably do a better job at handling cases like this. — Philip JF
@Guido I think the problem is not the unshared subSumme, but the unshared maxSumme. Leaving subSumme unshared costs double; leaving maxSumme unshared doubles the number of recursive calls, which leads to an exponential cost in the length of the list being recursed on. — Daniel Wagner

bheklilr bheklilr · Accepted Answer · 2013-12-13T00:18:02

So you've found the problem function. It's because for each list, you call subSumme many, many times. What you can do instead is map subSumme to each list passed to maxSumme, then find the maximum of those numbers:

maxSumme xs = maximum $ map subSumme xs

If you can't use maximum, you'll need to figure out how to implement that yourself =P

To explain the $ operator, it means to always run everything to the right before the left. It makes an expression like

f (g (h (i (j (k (l x))))))

into

f $ g $ h $ i $ j $ k $ l x

Be warned, this gets tricky with functions with multiple parameters. This wont compile

map $ (1+) $ replicate 10 1

because it's the same as

  map ((1+) (replicate 10 1))
= map ((1+) replicate 10 1))
= map (1 + replicate 10 1)
= map (1 + [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
         ^------ Can't add a number to a list!

But you could do

map (1+) $ replicate 10 1

Basically, all it's for is to remove the need for parentheses in a lot of cases.

Haskell method is too slow

1 Answers