C9 Lectures: Dr. Ralf Lämmel - Going Bananas

[EDN Admin]

Dr. Ralf Lämmel returns for an exploration of folds , aka bananas . This is lecture 5 in https://channel9.msdn.com/Tags/ralf-laemmel his C9 Lecture series covering advanced functional programming topics. Welcome back, Ralf! Were so happy to have you here! Why bananas, Ralf? Banana is functional programming slang for "fold"—an application of the http://en.wikipedia.org/wiki/Catamorphism catamorphic recursion scheme most widely known in the http://en.wikibooks.org/wiki/Haskell/List_processing higher-order list processing tradition of http://en.wikipedia.org/wiki/Bird-Meertens_Formalism Bird-Meertens Formalism and the Squiggol community. http://research.microsoft.com/en-us/um/people/emeijer/ Erik Meijer used to be known as the "banana man" because of his early research on the subject; he also co-authored http://academic.research.microsoft.com/Paper/296068.aspx the seminal paper with theoretical (categorical) foundations on the subject . Incidentally, the paper used the notation of so-called "banana brackets" (instead of using the plain string "foldr"), which sort of explains why we sometimes say bananas. There is no shortage of crazy paper titles on the subject, by the way: "Functional Programming with Bananas, Lenses, Envelopes, and Barbed Wire," " http://research.microsoft.com/en-us/um/people/emeijer/Papers/Bananas.pdf Bananas in Space : ...," " http://homepages.cwi.nl/~ralf/wgp00/ Dealing with large bananas ," " http://www.seas.upenn.edu/~sweirich/papers/itabox/MS-CIS-03-26.pdf Boxes go bananas : ...," " http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-3VTK49S-W&_user=10&_coverDate=11%2F30%2F1996&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d380f8c829a0576bfebf1c5a1d354d68&searchtype=a See more through lenses than bananas ," etc. More to the point, http://en.wikibooks.org/wiki/Haskell/List_processing#foldr foldr is the Swiss Army Knife in functional programming. Monoidal reductions of lists or mapping over lists and many other list-processing idioms can be modeled with the regular recursion operator foldr. Even a beginning lecture on functional programming would have to discuss foldr. Not discussing foldr in a Haskell course, however, is like not discussing for loops in a C# course. Indeed, the lectures on http://channel9.msdn.com/Shows/Going+Deep/Lecture-Series-Erik-Meijer-Functional-Programming-Fundamentals-Chapter-1 Graham Huttons introductory Haskell course covered the basics of foldr very well. However, a lot more interesting stuff concerning folds or, say, bananas becomes apparent when one becomes fluent in functional programming. For instance, foldr and friends suddenly make sense for container types other than the concrete list type. Foldr and friends even generalize to arbitrary algebraic datatypes in different ways. The combination of folds and monoids also helps us understand key aspects of parallel data processing. These are the more advanced banana subjects that are covered by Ralf Lämmels lecture this time. He has also contributed a stack of bananas papers over the years, and he draws from that interest. Learn more:
http://developers.svn.sourceforge.net/viewvc/developers/repository/ralfs-channel9-lectures/decks/bananas.pdf
Going Bananas lecture slide deck
http://developers.svn.sourceforge.net/viewvc/developers/repository/ralfs-channel9-lectures/code/bananas/ Download source code for this lecture
http://professor-fish.blogspot.com/2010/12/underappreciated-banana-and-its-buddy.html Ralfs blog

For the exercises/riddles in the slide deck:

Slide number (complexity): 12 (medium)
18 (medium)
21 (medium)
23 (easy)
24 (hard)
31 (hard)
34 (easy) <img src="http://m.webtrends.com/dcs1wotjh10000w0irc493s0e_6x1g/njs.gif?dcssip=channel9.msdn.com&dcsuri=http://channel9.msdn.com/Feeds/RSS&WT.dl=0&WT.entryid=Entry:RSSView:f497db42509940108e609e700144dba2

View the full article