On Jun 17, 2:36 pm, "Claus Reinke"
I'll work with Simon to investigate the runtime, but would welcome any ideas on further speeding up cafe4.
Just a wild guess, but those foldWithKeys make me nervous.
The result is strict, the step function tries to be strict, but if you look at the code for Data.IntMap.foldr, it doesn't really give you a handle for propagating that strictness. Unless the foldr definition is inlined into your code, the generic, non-strictly accumulating version might be called. Have you checked that this isn't the case?
Also, shouldn't the two foldWithKeys on dm be merged? And, while Maps are strict in their representation, putting them into a non-strict field of a data structure might lose that.
Claus -- thank you for the suggestions! Alas, it appears there's no strict foldWithKey in either Map or IntMap. Hence I had to cook one up with foldl' and fromList. I also merged both dm folds into one. The resulting tag is cafe5. It still gets killed by memory constraint at day 28. We're making progress here! :) -- Alexy