Python: functional programming with cons, car & cdr

Question

There is this problem that goes like this:

cons(a, b) constructs a pair, and car(pair) and cdr(pair) returns the first and last element of that pair. For example, car(cons(3, 4)) returns 3, and cdr(cons(3, 4)) returns 4.

Now, I have seen the solution, but I'm wondering if anybody can explain how to actually think to reach the solution?

1. cdr(cons(3, 4)): in what order are these two functions evaluated? I would normally think that cons(3, 4) are evaluated first, but that does not make sense in this case, because cons(3, 4) returns a function where arguments 3 and 4 are "integrated", so there is no way of singling out the arguments.
2. It seems to me that car(f) returns a function, so how can cons(3, 4) return 3? EDIT: typo, should be car(cons(3, 4)) instead of cons(3, 4)
3. I am obviously trying to solve this problem because I want to learn Python, but would you recommend me to skip these problems? I am tempted to do so by reading here: Why program functionally in Python?

Solution:

def cons(a, b):
    def pair(f):
        return f(a, b)
    return pair

def car(f):
    def pair(a,b):
        return a
    return f(pair)

def cdr(f):
    def pair(a, b):
        return b
    return f(pair)

print(car(cons(3,4)))
Output: 3
print(cdr(cons(3,4)))
Output: 4

Answer 1

In a(b()), b will always be evaluated first. I do not know of a single exception to this in Python. a would need to be a macro for the reverse to be true.

Note what the name of cdr and car's parameters are: f, as in "function". Each function accepts a function as an argument. This works though because, as you noted, cons returns a function.

In car(cons(3,4)), cons returns a function (locally known as pair). That function is then given to car, and car uses it here: f(pair). In this case, f is the function that was passed in. The complicated part here is that f is a function that accepts another function, and calls it with two arguments. Those two arguments are the data that was given to cons originally: 3 and 4.

---

cons(3, 4) does not return 3, car(cons(3,4)) does. cons(3, 4) returns a function that acts on the data that was given to it. In this case, car's pair function ends up throwing away the second passed argument (4), and instead returns the first (3).

---

Yes, stay far away from code like this for a while. Passing functions around is quite useful, but this code is more of an experimental toy. It's theoretical code to show a style (derived from a lisp like Scheme based on the terminology). There are many, simpler ways of achieving the same end result.

Practice simple examples of Higher Order Functions (like map and reduce), become proficient with them, then revisit this code. It will still be difficult to comprehend (because, this code doesn't lend itself to easy comprehension), but it will make more sense.