LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 July 16 2013

Joe
Member

[Exercise] more on function composition

Here's how Wikipedia defines function composition:

In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the next, and the result of the last one is the result of the whole.

For instance, here's a compose function in JavaScript that takes 2 arguments and return the composition of both:

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

function increment(x) {
    return x + 1;
}

function square(x) {
    return x*x;
}

>>> compose(square, increment) (5)
36

I can find 3 main issues in the compose function I wrote:

  • It assumes g is a function that takes one argument.

  • It assumes f is a function that takes one argument and that g(x) is of the correct type.

  • It can only take 2 arguments. You don't want to end up writing compose(f, compose(g, compose(...

The second point is particularly difficult to solve in languages with dynamic typing. So don't feel too bad about ignoring it. If f(g(x)) is not a valid call, it's the programmer's fault, not your function's.

However you want to solve the first and third point. In short:

Write a function that takes a variable number of function arguments and returns a function that takes a variable number of arguments and returns the result of the successive application of the earlier functions.

I should not be allowed to write stuff like that...

If you're completely new to this, here are a couple of topics you may want to get familiar with beforehand:

  • Higher order functions.

  • Variadic functions.

Offline

#2 July 16 2013

arithma
Member

Re: [Exercise] more on function composition

Sometimes we're stretching the word "exercise".

Offline

#3 July 17 2013

saeidw
Member

Re: [Exercise] more on function composition

I tried to approach this by constraining the functions so that each function takes a single input and returns a single output. These functions are easy to compose, so it's better to think in terms of these functions.

How do we transform a normal, multi-parameter Javascript function into one that takes a single input and returns a single output? Currying of course!

Consider:

function f (a, b, c) {
    return a + b + c;
}

function g (a) {
    return function g1 (b) {
        return function g2 (c) {
            return a + b + c;
        };
    };
}

f(1, 2, 3)  // => 6
g(1)(2)(3)  // => 6

f is a normal function that returns the sum of its arguments. We can implement f as a curried function by only accepting a single parameter and returning a function until we've finally received all the parameters. Once that happens, we can evaluate the result.

Since curried functions accept a single input and return a single output, the problem is reduced to "curry the functions, and then compose them just linke single-input-single-output functions".

Here's my naive implementation of curry(), it's based on this informative article.

function curry (fn) {
    function collectArgs (args, accumulatedArgs, numRemainingArgs) {
        var acc = accumulatedArgs.concat(args);

        if (0 >= numRemainingArgs) {
            return fn.apply(this, acc); 
        }

        return function () {
            var args = Array.prototype.slice.call(arguments);
            return collectArgs(args, acc, numRemainingArgs - arguments.length);
        };
    }

    var numFnArgs = fn.length;
    return collectArgs([], [], numFnArgs);
}

We rely on the fact that in Javascript, a Function object has a length property that tells us how many parameters it expects. We call collectArgs() with that number and empty arrays for the arguments passed and the arguments accumulated, respectively. collectArgs() will either evaluate the function if the correct number of arguments has been accumulated, or it will accumulate the arguments and return a function that, when called, will accumulate more arguments until the correct number is available.

We can use curry() like this:

var f = curry(function (a, b, c) {
    return a + b + c;
});

var add4 = f(2)(2); // partially apply f

add4(6);    // => 10

Now, all we have to do is implement compose() with the assumption that its arguments are curried functions. Note that we can be sure of this by currying the functions if they haven't been curried, I'll leave that as an exercise for you!

function compose (f, g) {
    return function () {
        var r = g.apply(this, arguments),
            rs = [r];

        return f.apply(this, rs);
    };
}

This is a straightforward translation of the compose() from the example. We return a function that first applies g() to its arguments, and then applies f() to the result. Note that since they're curried, f() and g() can accept as many arguments as they want, and the composition will still work.

For example:

var addstuff = function (x, y) {
    return x + y;
};

var mulstuff = function (x, y) {
    return x * y;
};

var dostuff = compose(addstuff, mulstuff);

dostuff(2, 3)(7);   // => 13

In this example, dostuff() passes its first two parameters to mulstuff(), which multiplies them to produce 6. It then passes that result to addstuff(). Since addstuff() expects two parameters, and it got only one, the result is a function expecting the remaining parameter. This is because addstuff() is a curried function, and we've partially applied it to one parameter. When we pass it the next parameter, 7, it evaluates the result of adding that to 6, which is 13.

You can think of this as a rough draft for a more general solution. The syntax can be improved with some more tinkering, and weird conditions like partially applying the inner composed function still need to be handled. Additionally, I haven't considered composing an unknown number of functions, but I know it's possible by generalizing the simple composition.

Offline

#4 July 17 2013

Joe
Member

Re: [Exercise] more on function composition

I originally spent the evening trying to come up with a clever combination of fold and apply. I didn't manage to do it. (Yet).

Instead, I found much easier and more straightforward. In Scheme:

(define (compose f g)
  (lambda (x) (f (g x))))

(define (compose-n . functions)
  (accumulate compose identity functions))


;; where identity is
(define (identity x) x)

It still needs a little bit of ironing, mainly make compose return a variadic function (or as @saeidw's solution suggests, currying).

Here's how I can test it:

(define (double x) (+ x x))
(define (square x) (* x x))

((compose-n double double square) 3)
;Value: 36

Offline

#5 July 19 2013

Magtheridon96
Member

Re: [Exercise] more on function composition

Compile this with g++ -std=c++11 -Wall -pedantic
(It requires G++ 4.8.1 because it's among the only feature-complete C++11 compilers available at the moment.)

#include <utility>
#include <string>
#include <iostream>
#include <functional>

template<typename Head, typename Tail> struct composer {
    Head head;
    Tail tail;
    composer(Head h, Tail t)
        : head(std::move(h)), tail(std::move(t)) {}
    template<typename... Args> auto operator()(Args&&... args) -> decltype(head(tail(std::forward<Args>(args)...))) {
        return head(tail(std::forward<Args>(args)...));
    }
};
template<typename Head, typename... Tail> struct composition_return_type {
    typedef composer<typename std::decay<Head>::type, typename composition_return_type<Tail...>::type> type;
};
template<typename Head> struct composition_return_type<Head> {
    typedef typename std::decay<Head>::type type;
};
template<typename Head> auto compose(Head&& head) -> typename std::decay<Head>::type {
    return std::forward<Head>(head);
}
template<typename Head, typename... Tail> auto compose(Head&& head, Tail&&... tail) -> typename composition_return_type<Head, Tail...>::type {
    return typename composition_return_type<Head, Tail...>::type(std::forward<Head>(head), compose(std::forward<Tail>(tail)...));
}

int main() {
    auto f1 = [](int x) { return x; };
    auto f2 = [](int x) { return x * 2; };
    auto f3 = [](int x) { return std::to_string(x); };
    auto f4 = [](std::string x) { return x + " - "; };
    auto f5 = [](std::string x) { return x + "This"; };
    auto f6 = [](std::string x) { return x + "Actually"; };
    auto f7 = [](std::string x) { return x + "Works."; };
    
    // This composes a function equivalent to f7(f6(f5(f4(f3(f2(f1( ... )))))))
    auto functor = compose(f7, f6, f5, f4, f3, f2, f1);
    
    auto test1 = std::bind(functor, 10);
    auto test2 = std::bind(functor, 45);
    
    std::cout << test1() << std::endl << test2() << std::endl;
}

C++11 templates are Turing-complete and we can do a lot of wonderful things with them c:

Last edited by Magtheridon96 (July 19 2013)

Offline

#6 July 20 2013

arithma
Member

Re: [Exercise] more on function composition

function compose(farr, fnext){
    function helper(farr, args, fnext){
        if(args.length==fnext.length)
            return fnext.apply(this, args)
        
        return function(){
            first = farr[0];
            var farrcurr = farr.slice(1);
            val = first.apply(this, arguments);
            var argscurr = args.slice(0);
            argscurr.push(val);
            
            return helper(farrcurr, argscurr, fnext);
        }
    }
    return helper(farr, [], fnext);
}

function add2(a,b){
    return a+b;
}

function mul2(a,b){
    return a*b;
}

function div2(a,b){
    return a/b;
}

function double1(a){
    return a*2;
}

f = compose([add2, mul2], div2);

// multilevel composition still sucks due to conceptual-types not matching (function that returns a function
g = function(a,b){
    return (compose([f(a,b)], double1));
}

console.log(f(1,1)(2,3))
console.log(g(1,1)(2,3))

This iteration homogenises types better:
gist file listing
The highlighted line is a weird problematic line. If it is switched with the next line, I think stacks are being messed up. I couldn't imagine how

fnextargs.push(f.apply(this,fargs));

could affect args. This has already frustrated me unstopped for more than 3 hours.

EDIT
Am not used to "undefined" variables getting set automatically causing global variables to be created. Feels like a newbie. I don't know how JS developers can possibly keep it straight. Weirdness issue solved. Here's the code:

Function.prototype.N = function(){
    if(this._length === undefined)
        return this.length;
    return this._length;
}

function compose(farr,fnext,name){
    var fnlength = 0;
    farr.forEach(function(f){fnlength += f.N()});
    fn = function(){
        var args = Array.prototype.slice.call(arguments);
        var argscpy = args.slice(0);
        var fnextargs = [];
        for(var i = 0, len = farr.length; i < len; i++){
            var f = farr[i];
            var fLen = f.N();
            var fargs = args.slice(0, fLen);
            fnextargs.push(f.apply(this,fargs));
            args = args.slice(fLen);
        }
        return fnext.apply(this,fnextargs);
    }
    fn._length = fnlength;
    return fn;
}

function add2(a,b){
    return a+b;
}

function mul2(a,b){
    return a*b;
}

function div2(a,b){
    return a/b;
}

function double1(a){
    return a*2;
}

f = compose([add2, mul2], add2, "    f");
g = compose([f], double1, "  g");
h = compose([g, double1], add2, "h");

console.log(h(1,1,20,3,100));

Last edited by arithma (July 20 2013)

Offline

#7 July 22 2013

arithma
Member

Re: [Exercise] more on function composition

@ Magtheridon96 A perfect teaser for the new C++ features I wanted to check out. Am starting to feel everyone else's sentiment towards the language though.
Where are you learning the new features from? A book? A site? Share :)

Offline

#8 July 22 2013

Magtheridon96
Member

Re: [Exercise] more on function composition

One word: StackOverflow

There are so many Questions and Answers on variadic templates and template metaprogramming.

I learned about the constructs like bind, move and forward from www.cppreference.com, and I'm also reading Concurrency in Action by Anthony Williams which happens to explain some of these constructs in detail while explaining the semantics of the std::thread constructor (which happens to be variadic). TMP is painful, but people with experience in functional languages shouldn't have a very bad time
(I dabbled in Haskell before and it helped~)

Offline

Board footer