[Haskell-cafe] Is this haskelly enough?
Bjorn Bringert
bringert at cs.chalmers.se
Wed Jul 18 04:52:32 EDT 2007
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
More information about the Haskell-Cafe
mailing list