Functional Programming – Understanding Banana Split and Fusion

functional programminghaskell

These terms got mentioned in my university course. Quick googling pointed me to some university papers, but I am looking for a simple explanation.

Best Answer

Even though 2 answers have already been provided, I don't think the "banana split" has been explained here yet.

It is indeed defined in "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire, Erik Meijer Maarten Fokkinga, Ross Paterson, 1991"; that article is hard to read (for me) due to its heavy use of Squiggol. However, "A tutorial on the universality and expressiveness of fold, Graham Hutton, 1999" contains a definition that is easier to parse:

As a simple first example of the use of fold to generate tuples, consider the function sumlength that calculates the sum and length of a list of numbers:

sumlength :: [Int] → (Int,Int)
sumlength xs = (sum xs, length xs)

By a straightforward combination of the definitions of the functions sum and length using fold given earlier, the function sumlength can be redefined as a single application of fold that generates a pair of numbers from a list of numbers:

sumlength = fold (λn (x, y) → (n + x, 1 + y)) (0, 0)

This definition is more efficient than the original definition, because it only makes a single traversal over the argument list, rather than two separate traversals. Generalising from this example, any pair of applications of fold to the same list can always be combined to give a single application of fold that generates a pair, by appealing to the so-called ‘banana split’ property of fold (Meijer, 1992). The strange name of this property derives from the fact that the fold operator is sometimes written using brackets (| |) that resemble bananas, and the pairing operator is sometimes called split. Hence, their combination can be termed a banana split!

Related Topic