Why functional programming matters
Friends Over the next few months I'm giving two or three talks to groups of *non* functional programmers about why functional programming is interesting and important. If you like, it's the same general goal as John Hughes's famous paper "Why functional programming matters". Audience: some are technical managers, some are professional programmers; but my base assumption is that none already know anything much about functional programming. Now, I can easily rant on about the glories of functional programming, but I'm a biased witness -- I've been doing this stuff too long. So this message is ask your help, especially if you are someone who has a somewhat-recent recollection of realising "wow, this fp stuff is so cool/useful/powerful/etc". I'm going to say some general things, of course, about purity and effects, modularity, types, testing, reasoning, parallelism and so on. But I hate general waffle, so I want to give concrete evidence, and that is what I particularly want your help with. I'm thinking of two sorts of "evidence": 1. Small examples of actual code. The goal here is (a) to convey a visceral idea of what functional programming *is*, rather than just assume the audience knows (they don't), and (b) to convey an idea of why it might be good. One of my favourite examples is quicksort, for reasons explained here: http://haskell.org/haskellwiki/Introduction#What.27s_good_about_functional_p... But I'm sure that you each have a personal favourite or two. Would you like to send them to me, along with a paragraph or two about why you found it compelling? For this purpose, a dozen lines of code or so is probably a maximum. 2. War stories from real life. eg "In company X in 2004 they rewrote their application in Haskell/Caml with result Y". Again, for my purpose I can't tell very long stories; but your message can give a bit more detail than one might actually give in a presentation. The more concrete and specific, the better. E.g. what, exactly, about using a functional language made it a win for you? If you just reply to me, with evidence of either kind, I'll glue it together (regardless of whether I find I can use it in my talks), and put the result on a Wiki page somewhere. In both cases pointers to blog entries are fine. Quite a lot of this is FP-ish rather than Haskell-ish, but I'm consulting the Haskell mailing lists first because I think you'll give me plenty to go on; and because at least one of the talks *is* Haskell-specific. However, feel free to reply in F# or Caml if that's easier for you. Thanks! Simon
Hi! My personal favourite is a neat (read: efficient and mostly write-only) way to balance AVL trees which I learned at a Haskell course on my university. This is the first implementation which comes to one's mind when playing with Trees:
data Tree a = L | N (T a) a (T a)
Balanceness is defined in terms of a tree's height:
height :: T a -> Int height L = 0 height (N l a r) = 1 + max (height l) (height r)
This gets the difference of the subtrees' heights: (Note that it could return a negative value, too.)
skew :: T a -> Int skew L = 0 skew (N l a r) = (height l)-(height r)
Our tree is balanced iff the skew is at most 1 for every subtree:
balanced :: T a -> Bool balanced L = True balanced t@(N l a r) | abs (skew t) <= 1 = balanced l && balanced r | otherwise = False
Now the interesting part. What if a tree is not balanced? Here do rotations come into the picture. There are several types of rotations which usually need some attention and are awkward to code in an imperative language. Of course one can do it in a functional language almost as awkward as in an imperative one, but the point is to use pattern matching like shown below:
rightRot :: T a -> T a rightRot (N (N x a y) b z) = N x a (N y b z) rightRot a = a
This is one of the simplest cases which makes it relatively easy to read. The thing is that this is a really fast implementation achieved at almost no effort. Also, it doesn't get harder than this:
leftRightRot :: T a -> T a leftRightRot (N (N x a (N y b z)) c v) = N (N x a y) b (N z c v) leftRightRot a = a
which can also be written as:
leftRightRot (N x a y) = rightRot (N (leftRot x) a y)
So I think this was the moment when I made up my mind to commit myself to Haskell & FP. Cheers, Zsolt
Simon Peyton-Jones wrote:
[...]
2. War stories from real life. eg "In company X in 2004 they rewrote their application in Haskell/Caml with result Y". Again, for my purpose I can't tell very long stories; but your message can give a bit more detail than one might actually give in a presentation. The more concrete and specific, the better. E.g. what, exactly, about using a functional language made it a win for you?
We [1] implemented an ad-hoc chat system in Haskell in the SEP [2] at the TU-Braunschweig. The ad-hoc (there is no central server, every node has the same behaviour) protocol [3] (not of our making) is rather complicated, as each node on the network has to detect the neighbouring network topology in order to route messages to their destination: A <-> B <-> C Besides, it has to handle netsplit and -merge situations: Two separate networks might be connected by the spawning of a new node in between or split by the disappearance of the latter. There are public and private IRC-like channels, the latter is encrypted by a symmetric cipher. Besides, there is an anonymous channel obscuring a message's origin. On top of that we built a nice gtk2hs GUI. The project homepage is http://sep07.mroot.net/index.html. I regret it's not in English :( - But the source code and documentation [4] are. You can build the documentation from the snapshot [5]. The interesting thing about the project is, that it provides a nice mixture of IO (network), purely functional protocol handling and related data structures and a graphical user interface (GTK). Besides, it was implemented by 3 other groups (two using Java, one using C++) as well. Comparing the results, you see that the Haskell implementation is not only more stable and provides more features, it also has about 70% less code. Let me know, if you're interested in details.
[...]
Hope this helps Stephan [1] 4 students: 2 experienced Haskell users and two newbies [2] a practical course where a non-trivial software project has to be planned, implemented and documented [3] http://sep07.mroot.net/documentation/draft-strauss-p2p-chat-09.txt [4] Complete repository available at: http://sep07.mroot.net:81/cgi-bin/darcsweb.cgi?r=SEP%202007%20-%20Ad-Hoc-Cha... [5] http://sep07.mroot.net/snapshots/Barracuda-1.0.2.tar.bz2 -- Früher hieß es ja: Ich denke, also bin ich. Heute weiß man: Es geht auch so. - Dieter Nuhr
participants (3)
-
Simon Peyton-Jones -
Stephan Friedrichs -
Zsolt Dollenstein