Functions Everywhere

Computer Science Level 2

Chris recently got addicted to functions and he presents his best implementation of functions to you:

function list_of_size(n) {
    function term(x) {
        return x * (x + 1);
    }
    function list_helper(count) {
        if (count > n) {
            return function(f) {
                return -1;
            };
        } else {
            return function(f) {
                return f(term(count), list_helper(count + 1));
            };
        }
    }

    return list_helper(1);
}

function head(f) {
    return f(function (p, q) { return p; });
}

function tail(f) {
    return f(function (p, q) { return q; });
}

function sum(list) {
    if (head(list) === -1) {
        return 0;
    } else {
        return head(list) + sum(tail(list));
    }
}

What is the value of sum(list_of_size(3)) ?

8 20 36

1 solution

Agnishom Chattopadhyay
Sep 1, 2016

The function list_of_size returns a function which essentially encodes a linked list in some sense.

The $r$ th term of this list consists of $r (r+1)$

So, we want $\sum^3_{r=1} r(r+1) = 20$

This implementation of a linked list is essentially like the idea of lists in lambda calculus

Functions Everywhere

1 solution

0 pending reports