Ah, our old friend Maximum Segment Sum. Given a list of integers, find the highest sum of any set of adjacent integers. The list [ 1, 2, 3, -4] has an MSS of 6 (1 + 2 + 3). The solution is deceptively simple:
mss = max º sum* º (flatten º tails* º inits)
Briefly explained…
inits() returns all the initial segments of a list in order of increasing length. So the inits of [1, 2, 3] is [ [1], [1,2], [1,2,3] ]
tails() returns all the trailing segments of a list in order of decreasing length. So the tails of [1, 2, 3] is [ [1,2,3], [2,3], [3] ]
Calculating the MSS is as simple as taking the inits of a list, taking the tails of the result, find the sum of each element in that result, and return the maximum entry. Simple, right?
Solving this is a great way to practice functional programming, which I did using Groovy in Function Calisthenics a few months ago, and again last night using F#.
The F# and Groovy results can be seen side by side here: http://www.hamletdarcy.com/files/2008/FsharpVsGroovy.html (I suggest opening it up in a new window big enough so that the lines don’t wrap).
Which begs the question, “Why would you ever want to compare F# (or OCaml) to Groovy?”
Because it explores the answers to a few other questions:
Are dynamically typed languages more concise than statically typed ones? Maybe the comparison between Java and Groovy isn’t a fair comparison, because the results here show F#/OCaml being more concise.
How awful is the F#/OCaml syntax? You can make your own conclusion, but it might be worth spending a few hours with the language before pronouncing a victor. I personally have found the freedom from curly braces and good recursion support a Good Thing.
Do I want to give F#/OCaml a try? That’s kinda the point of writing a post about the language, isn’t it?
So here goes…
Conciseness – The F# version is shorter, there’s no denying that. You also don’t need to add any type information despite the fact that the language is statically typed and the IDE shows you compiler errors as they happen. Also, the F# libraries offer much better support for functional constructs. For instance, the map_concat function doesn’t exist in Groovy, so much of the Groovy code is simply reducing a List of Lists of Lists to a List of Lists. Groovy support for closures and collections is good, but check out the F# documentation and see all functions you wish you had. There is certainly a learning curve to understanding the map*, fold*, and reduce* functions, but I contend that it’s worth the time to learn the fundamentals of Computer Science, which these concepts can rightly be categorized as.
Also, concise List and Map (and Sequence!) creation using the [ a, b, c ] notation is a wonderful thing. But this is an issue with Java, not statically typed languages in general.
The Awful Syntax – Come on, is it really that bad? Sure there is a new set of libraries to learn… but you’re not exactly investing in learning the .NET libraries, just the F# ones. I don’t know a thing about .NET and this was fairly simple. It doesn’t even really rely on the .NET libraries in this example (under the covers it does because it’s implemented in a .NET language and provides interoperability, but that’s another matter). Ricky Clarkson explores having to learn a new syntax in his post “In Defence of (0/:l)(_+_) in Scala”, which includes a quote from David MacIver: "Optimising your notation to not confuse people in the first 10 minutes of seeing it but to hinder readability ever after is a really bad mistake." Exactly. Maybe its time we ditch the C++/Java syntax. It’s not that hard.
Giving F#/OCaml a shot – Let me be clear: Learning F# is not the same as learning .NET. There are plenty of directions online for running it under Mono in Mac/Linux, and the F# install comes with an install-mono.sh shell script. I got it to run on an EEE PC with Xandros Linux without much effort. And there have been plenty of “wow” moments learning F# including wondering how the heck the compiler knows about my types and the satisfaction of finally understanding what “('a -> 'b) -> 'a list -> 'b list” means (Hint: it is a type signature that takes a function and a list and returns another list).
And why would you not want to make this comparison? Groovy is not a functional language and doesn’t advertise itself to be. Closure/lambda support in Groovy is good, and enables a functional style, but it’s not quite a level playing field. A comparison of the languages in an Object Oriented style might well yield different results.
Anyway, give it a shot, my friends, give it a shot. Perhaps the sweet F# handout can shed some light: http://hamletdarcy.blogspot.com/2008/07/f-handout-available.html
12 comments:
How does the performance of each stack up?
You could have used a different (more pleasant) notation for the ranges ;-)
(0..<list.size())
instead of
(0..list.size()-1)
Nice post.
Yes please! Submit your improvements to both scripts by posting a comment or emailing me (hamletdrc@gmail.com).
Also, I'd love to see a Ruby and Scala version... just please try to follow the functional style and function names so that a side by side comparison can more easily be made. (and yes, i realize that comparing non-idiomatic Ruby code to idiomatic F# code does not create a level playing field. this is just an exploration).
Nice blog. I would probably solve the Groovy version with something like this:
List.metaClass.inits = { -> (0..<delegate.size()).collect{ delegate[0..it] } }
List.metaClass.tails = { -> (0..<delegate.size()).collect{ delegate[it..<delegate.size()] } }
def segs = { list -> list.inits()*.tails().sum() }
def solve = { list -> segs(list)*.sum().max() }
def numbers = [31,-41,59,26,-53,58,97,-93,-23,84]
def solution = solve(numbers)
println "Maximum Segment Sum of $numbers is $solution"
Or, using the same trick used in F# for shorterning tails():
List.metaClass.inits = { -> (0..<delegate.size()).collect{ delegate[0..it] } }
List.metaClass.tails = { -> delegate.reverse().inits() }
def segs = { it.inits()*.tails().sum() }
def solve = { segs(it)*.sum().max() }
def numbers = [31,-41,59,26,-53,58,97,-93,-23,84]
def solution = solve(numbers)
println "Maximum Segment Sum of $numbers is $solution"
A slight variation using the latest metaClass DSL (trunk only):
List.metaClass {
inits{ (0..<delegate.size()).collect{ delegate[0..it] } }
tails{ delegate.reverse().inits() }
}
def segs = { it.inits()*.tails().sum() }
def solve = { segs(it)*.sum().max() }
def numbers = [31,-41,59,26,-53,58,97,-93,-23,84]
println "Maximum Segment Sum of $numbers is ${solve numbers}"
Or using the latest mixin notation (again trunk only):
class ListUtils {
static inits(List list) { (0..<list.size()).collect{ list[0..it] } }
static tails(List list) { list.reverse().inits() }
}
List.metaClass.mixin ListUtils
def segs = { it.inits()*.tails().sum() }
def solve = { segs(it)*.sum().max() }
def numbers = [31,-41,59,26,-53,58,97,-93,-23,84]
println "Maximum Segment Sum of $numbers is ${solve numbers}"
@paulk you rule. And so does Groovy, based on your examples. If I have time I'll try the open classes approach in F# and see how it looks compared to these. Nothing beats staying up late Friday nights programming :)
I updated both Groovy and F#'s version to use open classes / mixins and reposted the whole bit here: http://www.hamletdarcy.com/files/2008/FsharpVsGroovy2.html
sorry, for some reason blogger chopped the 'l' off the .html in the last link
Try this: http://tinyurl.com/5e74vl
instead of :
http://hamletdarcy.blogspot.com/2008/07/awesome-new-groovy-mixin-syntax-and-fs.html
and
I would have written the F# like this:
open Seq
let inits seq = { for i in 1 .. length seq -> take i seq }
let segs seq = concat (map (List.rev >> inits) (inits seq))
let solve list = Seq.fold1 max (map (fold (+) 0) (segs list))
let numbers = [31; -41; 59; 26; -53; 58; 97; -93; -23; 84]
do printfn "Maximum Segment Sum of %A is %d" numbers (solve numbers)
The weird use/nonuse of def is because you're using groovy as a script rather than as a class. When you use it as a script (i.e. you put code into the toplevel, not in a class), using vs. not using def has a special meaning, in that def puts the code into a separate space as though you'd put it into a class (IIRC). That's why you do not use def--you want the function to have the same lexical scope as the rest of the program.
Groovy does this because normally one writes groovy code with classes, but when you want a script, it's easier to have a simplified style. I don't agree with this, but it makes some sense to me.
Post a Comment