Functional Programming Crib Sheet #1 (the basics)

I've been learning functional programming over the last few months, mostly in Java and mostly with the TotallyLazy library (other libraries do exist).

It's quite a paradigm shift. To help me cope, I've compiled a crib sheet.


Reduce

"The reduceLeft method applies the passed function to the first two elements ... then applies it to the result of the first application and next element... and so on, all the way through the list." [1]

Reduce right "applies binary operation op between successive elements returned by non-empty iterator it, going right to left".

A reduce requires at least one element in the collection it works with as a reduce on a collection with one element trivially maps x to x.

TotallyLazy example


import static com.googlecode.totallylazy.Sequences.sequence;
import com.googlecode.totallylazy.Callable2;
.
.
        Callable2 reduceFn
            = new Callable2() {

            public Integer call(Integer a, Integer b) throws Exception {
                return a + b;
            }
  
        };
.
.
        sequence(1, 2, 3).reduce(reduceFn);


Produces a single integer, 6.


Folds

"A fold left operation ... involves three objects: a start value z, a list xs, and a binary operation op. The result of the fold is op applied between successive elements of the list prefixed by z." [1]

So, a fold left would look like:

op(op(op(z, a), b, c)

Or graphically:

Fold right produces right leaning trees. For instance:

op(a, op(b, op(c, z)))

or graphically:

The value z is sometimes called the seed.

Maths example

When a function is associative, you won't really see the difference between left and right folds. For instance:

(((4 + 3) + 2) + 1) = 10 = (4 + (3 + (2 + 1)))

because addition is associative.

Subtract is not, however. Therefore:

(((4 - 3) - 2) - 1) = -2 != (4 - (3 - (2 - 1))) = 2

Scala example

The Scala example is similar to the above maths but remember the seed. This will change the result but the method is the same:

    val ints: List[Int]            = List(4,3,2,1)
    def subtract(x : Int, y : Int) = { x-y }
    println(ints.foldRight(0)(subtract)) // 2   = (4 - (3 - (2 - (1 - 0)))
    println(ints.foldLeft(0)(subtract))  // -10 = ((((0 - 4) - 3) - 2) - 1)

Although fold and reduce are conceptually similar, reduce will error on an empty List.

    val abc = List("A", "B", "C")
    def myConcat(x : String, y : String) = {x + y}

    println(abc.foldRight(" the end")(myConcat)) // "ABC the end"
    println(abc.foldLeft("start: ")(myConcat))   // "start: ABC"
    println(Nil.foldRight("the end")(myConcat))  // "the end"
    println(Nil.foldLeft("the start")(myConcat)) // "the start"

    println(abc.reduceRight(myConcat))   // "ABC"
    println(abc.reduceLeft(myConcat))    // "ABC"
//    println(Nil.reduceRight(myConcat)) // blows up: Exception in thread "main" java.lang.UnsupportedOperationException: Nil.reduceRight
//    println(Nil.reduceLeft(myConcat))  // blows up too

TotallyLazy example

import static com.googlecode.totallylazy.Sequences.sequence;

import com.googlecode.totallylazy.Callable2;

.

.

        Callable2 add 

            = new Callable2() {

            public Integer call(Integer a, Integer b) throws Exception {

                return a+b;

            }

        };

.

.

        sequence(1, 2, 3).fold(1, add);

Produces a single integer: 7


Zip

Zip is NOT a cartesian product.

"The two arrays this.contents and that.contents are transformed into an array of pairs (as Tuples2s are called) using the zip operator. The zip method picks corresponding elements in its two arguments and forma an array of pairs. ...

"If one of the two operand arrays is longer than the other, zip will drop the remaining elements." [1]

TotallyLazy example

import static com.googlecode.totallylazy.Sequences.sequence;

.

.

    sequence(1, 2, 3, 4).zip(sequence(4, 5, 6))

Produces Pairs that look like:

[1,4],[2,5],[3,6]

Map

"Map[f, expr] - return the list that results from executing the function f on each element of an expr" [4].

TotallyLazy example

import static com.googlecode.totallylazy.Sequences.sequence;

import com.googlecode.totallylazy.Callable1;

.

.

        Callable1 add3 = new Callable1() {

            public Object call(Integer input) throws Exception {

                return input + 3;

            }

        };

.

.

        sequence(1, 2, 3, 4).map(add3)

Produces a Sequence that looks like:

4,5,6,7

Flat Map

This is a map then a flatten, that is it applies a function to a list and then flattens the results.

"The flatMap operator is similar to map, but it takes a function returning a list of elements as its right operand. It applies the function to each list element and returns the concatenation of all function results." [1]

"In mathematics, flat functions are called associative." [4]

TotallyLazy example

import static com.googlecode.totallylazy.Sequences.sequence;

import com.googlecode.totallylazy.Callable1;

.

.

        Callable1, ? extends Iterable

            = new Callable1, Iterable

            public Iterable

                    throws Exception {

                return input.map(add3);

            }

        };

.

.

        sequence(sequence(1, 2, 3), sequence(4, 5)).flatMap(add3Flatten);

Note how this produces a collection of collections that looks like:

{ {1, 2, 3}, {4, 5} }

Produces a Sequence like:

4,5,6,7,8

Partial function application


"Partial function application says "if you fix the first arguments of the function, you get a function of the remaining arguments" " [5] This means you can add one parameter now to the function and another later.

TotallyLazy example 


import com.googlecode.totallylazy.Function2;
.
.

    public Function2 sum() {

        return new Function2() {

            public Integer call(Integer a, Integer b) throws Exception {

                return a+b;

            }

        };

    }

.

.

Then, evaluation the sum of two numbers, 1 and 2 is trivial:

        sum().apply(1,2);

But if we wanted to add them partially:

        final Function1 onePlus = sum().apply(1);

Now it's part evaluated. At some later date, we might want to complete it, thus:

        onePlus.apply(2);

Which returns the integer 3.

Incidentally, the oder can be flipped with:

        sum().flip().apply(1);

Although this would make no difference in the case of addition.

Memoization

"In computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs." [2]

The example Wikipedia gives is that of factorial:

x! = x * (x-1) * (x-2) *...

If you've calculated 5! (5*4*3*2*1 = 120) then 6! is just this times 6 (because 6! = 6 * 5 * 4 ... = 6 * 5!).


Higher Order Functions

A "higher-order function (also functional form, functional or functor) is a function that does at least one of the following:

• take one or more functions as an input
• output a function" [2]

An example familiar in mathematics is the differentiator operator. Take the function:

f(x) = x^3

and the higher order differentiation operator

d
-
dx

then this operator takes a function and returns a function:

d(f(x))
------    = 3(x^2)
  dx

In summary, it takes a function and returns a function.


[1] Programming in Scala, Odersky.
[2] Wikipedia.
[3] Wikipedia.
[4] Sal Mangano's "Mathematica Cookbook" p26.
[5] Wikipedia.