Functional Programming

Topics:

• Currying
• Partial Evaluation
• Memoization
• Closures
• Lambda Expressions
• Recursion
• Reactive Programming (coming soon)

Functional Programming - Currying

Sample Code:

As you can see this function accepts two integers and returns one this is not a curried function.

            add :: (Integer, Integer) -> Integer
        

This function takes one integer, followed by a function that takes an integer, and finall returns an integer, this is an example of currying.

            add :: Integer -> Integer -> Integer
        

Functional Programming - Currying

Currying is often confused with partial-evaluation, however the key difference is with currying you are not infact creating a function accepts less than the repuired number of arguments, you are actually creating a chain of functions that each accept one function.

functional programming - partial application

A way to call a function that takes multiple arguments while providing a fewer arguments than required

Yields a new function that accepts the remaining arguments.

Regular partial application done by most languages simply binds the given arguments using closures (we'll explain later)

True 'partial evaluation' will actually invoke parts of this function

functional programming - partial application

This is a basic function that accepts 3 parameters and returns the average. This is a partial application.

        average x y z = (x + y + z) `div` 3
        

functional programming - partial application

Here we are partially applying the function we created earlier.

        average x y z = (x + y + z) `div` 3

        first = average 1

        second = first 2

        third = second 3
        

functional programming - memoization

Given an operation whose arguments completely determine its output, repeated calls to that operation with the same arguments will always produce the same output.

Memoization is a programming technique that takes advantage of this by recording the result of each invocation of an operation against the given arguments, and, when given the same arguments again, returns the stored result instead of invoking the operation again.

functional programming - closures

The concept of closure is the concept of letting a function have access to things that are scoped around it, and tying the lifetime of those things to the lifetime of the function.

        function findAverage(x, y, cb) {
            function findSum() {
                return x + y;
            }

            var result = fundSum() / 2;

            cb(result);
        }
        

functional programming - memoization

Here is a very basic example of memoization in Python that wraps a function in a object to memoize it.

        def memoize(f):
            memo = {}
            def delegate(*args):
                if not args in memo:
                    memo[args] = f(*args)
                return memo[args]
            return delegate

        def buildURI(a, b, c, d):
            return a + "://" + b + ":" + `c` + "/" + d

        buildURI = memoize(buildURI)
        

functional programming - memoization

Here is a proper example in Haskell

        times a  b = a * b

        timesM f' x y = do
            return $ times x y

        type StateMap a b = State (Map a b) b

        memoizeM t x y = evalState (f x y) Map.empty where
            g x y = do
                y <- t f x y
                m <- get
                put $ Map.insert x y m
                newM <- get
                return y
            f x y = get >>= \m -> maybe (g x y) return (Map.lookup x m)

        val x y = memoizeM timesM x y
        

functional programming - lambda expressions

Lambda expressions are functions not bound to an identifier, a common example of this is in-line functions.

Something we have done many times in javascript is a perfect example, callbacks:

        function findSum(x, y, cb) {
            var result = x + y;
            cb(result);
        }

        findSum(1, 2, function(x) {
            window.alert(x);
        });
        

functional programming - lambda expressions

Again in a functional language, with no side-effects we demonstrate a very similar piece of code:

        findSum :: Integer -> Integer -> (Integer -> Integer) -> Integer
        findSum x y f = (f(x+y)) 

        main = 
            print(findSum 2 3 (\x -> x * 2))
        

functional programming - recursion

Recursion is not a concept unique to functional programming, however the important note is that in functional programming their are no loops.

        countToTen x =
            if x < 10 then
                countToTen(x + 1)
            else
                x
        

OOP Dovetailing

• each/filter/transform/map/reduce: using data structures in functional fashion
• Lambda expressions (function object, if language not supported) enable 'call by continuation'
• First class functions let you pass existing functions as callbacks/continuations
• Promises (futures) are an elegant OO construct for functional continuations
• Anonymous objects are a lot like closures
• Currying allows you to eliminate wrapper functions -- simpler, cleaner
• For code written in functional style, memoization is a practically free hot path optimization

List processing

            String salutation = // pure functional expression
                customers.filter((Customer c) -> { c.lastName == "Smith"; }) // lambda
                    .transform((Customer c) -> { return capitalize(c.firstName); }) // map/reduce paradigm
                    .reduce("", (String name, String rest) -> { rest.append(" ").append(name); })
        

Promises

            Promise promise = executor.submit({ /* do something expensive */ });
            promise.andThen(println); // now output the result (first class function; not pure functional!)
        

Functional on the Architecture Level: Bottom-up Design

• Opposing approach to feature- or system-driven design
• Understand the problem domain as clearly as possible, from a technical standpoint
• Define a domain-specific language (DSL) which simplifies that component's implementation
• Repeat, extending DSL horizontally and/or vertically