I am reading Introduction to Functional Programming with Haskell (http://web.comlab.ox.ac.uk/oucl/publications/books/functional/) and was very impressed by the elegance of the solution to the maximum segment sum. The mss of the sequence

is 7, the sum of [5, -2, 1, 3]Code:[-1, 2, -3, 5, -2, 1, 3, -2, -2, -3, 6]

Bird's rather awesome solution to this is

(Edit - apols, can't get indetation right on haskell code...)Code:mss = maxlist . scanr (maxZero) 0 where maxZero x y = 0 `max` (x + y) maxlist = foldr1 (max)

This manages to be at once dense and not at all unreadable, even for someone learning the language...and I wondered what it would look like in other languages.

What would this look like in your favourite language? Bring me your scheme, your assembler, your perl! :-) Java lovers win kudos for daring to show their face :-)

The only one I've tried so far is python. I thought it would be pretty concise too, as lists are home turf and there is some support for higher order funtions, but I was surprised in the end at how may hoops I had to jump through. Python doesn't have anything like scanr and in the book Bird begins with a more easily understandable version

so I decided to start there, recreating the haskell builtins concat (flatten a list one level), init (return all initial segments of a list) and tails (return all final segments of a list). I also needed to work around the fact that in python list.extend returns None, which is broken IMHO:Code:mss = maxlist . map sum . segs where segs = concat . map inits . tails

python Code:from operator import add def mss(lst): if len(lst) == 0: return 0 segs = getSegs(lst) return reduce(max, map ((lambda x: reduce(add, x)), segs)) def getSegs(lst): return concat(map((lambda x: inits(x, 0)), tails(lst))) def myExtend(lst, val): lst.extend(val) return lst def tails(lst): if len(lst) == 0: return [] return myExtend([lst], tails(lst[1:])) def inits(lst, count): if count > len(lst): return [] return myExtend([lst[0:count]], inits(lst, (count + 1))) def concat(lst): """flatten 1 level and remove empty lists, because python's map won't deal nicely with them.""" lst2 = [] for l in lst: for m in l: if m != []: lst2.append(m) return lst2

So 1 Nil to haskell, and not only because of the builtins. I am no pythonista and hope that someone will prove me wrong with a better version than this.

Disclaimer: this problem is ideal for a language like haskell, because it specialises in recursion over structures and the point-free and functional composition styles (omitting params from function definitions and syntax like f . g) make it possible to express this all very cleanly.

agrees : I think it's great you're using it a lot, since noone else is :)