[Haskell-cafe] Is this haskelly enough?

[Bjorn Bringert]

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