On Jul 18, 2007, at 2:13 , ok wrote:
On Jul 17, 2007, at 22:26 , James Hunt wrote:
As a struggling newbie, I've started to try various exercises in order to improve. I decided to try the latest Ruby Quiz (http:// www.rubyquiz.com/quiz131.html) in Haskell.
Haskell guru level: I am comfortable with higher order functions, but never think of using the list monad.
Developing the answer went like this: - find all sublists - annotate each with its sum - find the best (sum, list) pair - throw away the sum
best_sublist = snd . maximum . annotate_with_sums . all_sublists
All sublists was easy:
all_sublists = concatMap tails . inits
Confession: the one mistake I made in this was using map here instead of concatMap, but the error message from Hugs was sufficiently clear.
Annotating with sums is just doing something to each element, so
annotate_with_sums = map (\xs -> (sum xs, xs))
Put them together and you get
best_sublist = snd . maximum . map (\xs -> (sum xs, xs)) . concatMap tails . inits
The "trick" here is that as far as getting a correct answer is concerned, we don't *care* whether we compare two lists with equal sums or not, either will do. To do without that trick,
best_sublist = snd . maximumBy c . map s . concatMap tails . inits where s xs = (sum xs, xs) f (s1,_) (s2,_) = compare s1 s2
Confession: I actually made two mistakes. I remembered the inits and tails functions, but forgot to import List. Again, hugs caught this.
However, the key point is that this is a TRICK QUESTION.
What is the trick about it? This is a well known problem called The Maximum Segment Sum problem. It's described in a paper "A note on a standard strategy for developing loop invariants and loops" by David Gries (Science of Computer Programming 2(1984), pp 207-214). The Haskell code above finds each segment (and there are O(n**2) of them, at an average length of O(n) each) and computes the sums (again O(n) each). So the Haskell one-liner is O(n**3). But it CAN be done in O(n) time. Gries not only shows how, but shows how to go about it so that you don't have to be enormously clever to think of an algorithm like that.
What would be a good exercise for functional programmers would be to implement the linear-time algorithm. The algorithm given by Gries traverses the array one element at a time from left to right, so it's not that hard. The tricky thing is modifying the algorithm to return the list; it might be simplest to just keep track of the end-points and do a take and a drop at the end.
I think it is at least mildly interesting that people commented about things like whether to do it using explicit parameters ("pointful" style) or higher-order functions ("pointless" style) and whether to use the list monad or concatMap, but everyone seemed to be happy with a cubic time algorithm when there's a linear time one.
Well, the original poster wanted advice on how to improve his Haskell style, not algorithmic complexity. I think that the appropriate response to that is to show different ways to write the same program in idiomatic Haskell. /Björn