CS1101S

Lecture 6: Function Composition

31 August 2012

Martin Henz

Overview

• Leader board!
• Some admin + words of advice
• Function composition, fold
• Lambda calculus

Leader board

Let's take a look!

Some Administration

Robot Project Groups

Groups of 3 or 4

Send email to Avenger Wang Sha wangshasg@gmail.com by 28/9
(end of midterm break)

Students who do not have a group will be randomly assigned

Forum Participation

Leads to Experience Points

Grading policy

• Relevance of post for classes / missions
• Effort put into writing
• Impact: Help provided, discussions generated
• Frequency

Overview

• Function Composition
• Fold
• Lambda calculus

Function Conmposition

In mathematics: (f g)(x) = f(g(x))

function compose(f, g) {
    return function(x) { return f(g(x)); };
}

var squared_factorial =

compose(square, factorial);

Remember sum?

function sum(term, a, next, b) {
    return (a > b) ? 0
                   : term(a)
                     +
                     sum(term, next(a), next, b);
}

Can we abstract the summation idea?

Fold

function fold(op, f, n) {
    return (n === 0) 
           ? f(0)
           : op(f(n), fold(op, f, n - 1));
}

Defining power with fold

function fold(op, f, n) {
    return (n === 0) 
           ? f(0)
           : op(f(n), fold(op, f, n - 1));
}
function power(b, e) {
    return fold(function(x, y) { return x * y; },
                function(x) { return b; },
                e - 1);
}

Your turn

sum_of_odd_integers(11)

sum_of_digits(123)

sum_of_digits

function sum_of_digits(n) {
    return fold( function(x, y) { return x + y; },
                 function(k) { return kth_digit(n, k); },
                 count_digits(n)
               );
}