[Haskell-cafe] Is this haskelly enough?

[ok]

> 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.