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

The problem you have shown can also be solved in this way.

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

def car(pair):
    return pair[0]

def cdr(pair):
    return pair[1]

This is how you will use it:

lst = cons(1,cons(2,3))

# Get the first element of lst
print(car(lst))

# Get the second element of lst
print(car(cdr(lst)))

# Get the last element of lst
print(cdr(cdr(lst)))

Output:

1
2
3

I'm only showing this so that you can see that there is more than one way to solve that problem, and the way you discovered is very rarely done in python. Anyone thinking to solve this in python will 99% of the time do it the way I've shown here.

Now on to your problem.

---

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)

First let's talk about these functions using some haskell function notation so that you can see the full type of these functions:

cons::(a, b) -> (((a, b) -> c) -> c)

cons is a function that takes two parameters a, and b, then it returns a function f which takes another function which when given the parameters (a,b), returns c, where c could be a or b, or something else. f then returns the value of c.

What a mouthful!

Another way to think of it is that the function f (((a, b) -> c) -> c) returned by cons is used to forward a and b to any operator (or mapping function) which wants to act on a cons. This operator returns c. f then simple returns whatever this mapping function returns, which happens to be c.

For now don't worry what c is. Just think of it the result of applying a function to a cons.

car::(((a, b) -> a) -> a) -> a

car defines a possible mapping from (a,b) to c, and returns the value of calling f with this mapping.

car takes a function f that wants a mapping from the input (a,b) to some output c. In this case, car defines the mapping as (a, b) -> a which means any function f which is passed to car will return the first argument of (a,b), which is just a. And that is what car will return.

cdr::(((a, b) -> b) -> b) -> b

Similar to car, but the mapping defined by cdr returns b instead of a.

---

Notice how similar the input for cdr and car are to the function (f) returned by cons? This is why I just called their inputs f

---

Now to answer some of your questions:

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.

In light of the explanation I gave above, the function returned from cons is exactly the same type as the one expected by cdr. Now all cdr has to do is supply a mapping function to f and return whatever f returns.

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)

car(f) does not necessarily return a function. See the type signatures above. It just returns whatever f returns and if that happens to be a function, then that's what it will return a function.

In general, car returns the first element of a cons. In this case, since cons(3,4) returns a function (f) and this function is passed to car, then car will supply this function with another function that chooses the first of it's arguments, which is 3 in this case. This 3 is now the result of car(cons(3,4).

I hope that clears things up.

Answer 2

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.

Answer 3

The code You pasted is meant to be used like this:

First, You define Your pair:

f = cons(3, 4)

After that, You define a function that works on pairs:

add = lambda x, y: x + y

Now, You can use Your "pair" like this:

f(add)

output:

7

So, what it does is: It converts Your pair into a function that can "execute" functions on pairs with the defined pair as arguments. car and cds can actually "convert" your pair-function back and return an element.

Edit:

In case You are not familiar to lambda expressions, see this tutorial.

For now, You could also go with

def add(x, y):
    return x + y

and use it just the same way. :)