CODEWITHSUNDEEP
haskelloptimization
Cilenco
Cilenco

Reputation: 7117

Haskell method is too slow

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.

Upvotes: 1

Views: 392

Answers (1)

bheklilr
bheklilr

Reputation: 54058

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.

Upvotes: 3

Related Questions