[Solution]Problem 20: Implement car and cdr functions[Jane Street]

Functional Programming, Closures, Anonymous Functions

Problem

This problem was asked by Jane Street.

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

Given this implementation of cons:

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

Implement car and cdr.

Understanding the question

To those of you that don’t have experience with Functional Programming, this question will seem very confusing. What is this format? Why do we do this? We’ll cover all this.

First, we should understand the implementation of cons. Cons is a function. In plain text, it does the following

# create cons function, that accepts two parameters, a and b
   # inside cons:
      # create pair function that accepts one parameter, f (must be a function)
         # inside pair:
               # call f function with arguments a and b and return the output
         # end pair
      # return pair function
   # end cons

So why do we do this? Look at how well our implementation generalizes. We can pass any function f to our pair function and it will work. This generalization is a hallmark for functional programming. Functional programming is an extremely powerful programming paradigm that is very useful in many cases. Working with it will give you a fingertip feel for recursive and mathematical thinking, which is why I will occasionally share such problems in this newsletter.

An illustration of scoping in the functional space.

Now that we know that let’s talk about usage. We would declare a cons object by doing the following:

closure1= cons(3,4) #in the example
closure2= cons(3,cons(4,1)) 
closure3= cons(3,[29]) 
closure4= cons(3,{'a':1}) 

These are all valid according to our implementation. This ability to handle generalization is why functional programming is extremely powerful and you should at least try to learn the basics.

Testing out the results from these declarations

closure3= cons(3,[29]) 
closure4= cons(3,{'a':1}) 

print(closure3) #<function cons.<locals>.pair at 0x7f87bfc40160>

print(closure4) #<function cons.<locals>.pair at 0x7f87bfc401f0>

We see that Python considers the closures as functions, which is what we expect. Specifically, each closure is a function implementation with a certain set of values. If this is confusing, I would recommend scrolling down and copying the code in the solution into an editor/online compiler. Look at the outputs and it should help you understand what’s going on.

Solution

This is an example of using closures to store data. Read into them a bit to fully understand the solution.

Look at the signature type of cons to retrieve its first and last elements. cons takes in a and b, and returns a new anonymous function, pair. pair itself takes in f, and calls f with a and b.

So the input to car and cdr is pair. To get a and b back, we must feed it yet another function, one that takes in two parameters and returns the first (if car) or last (if cdr) one. This, and a few more examples, would look the following.

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

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

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

def mult(pair): #how can we generalize this? Good excercise for you
    return pair(lambda a, b: b*a)

c=cons(3,4)
print(mult(c))

##
c2=cons(3,cons(4,1))
print(cdr(c2))

closure3= cons(3,[29]) 
closure4= cons(3,{'a':1}) 

print(closure3)
print(closure4)

print(cdr(closure3))
print(cdr(closure4))

This question and solution might seem weird at first, but the goal of these is to get you exposed to functional programming, anonymous functions, and closures. Learning these will benefit you in your day-to-day programming and interviews.

Bonuses/Promotion (Get Free Stuff)

Have anything to say to me? Use the links below.

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

For most of my students, mock interviews have been very helpful. Enough mock interview practice is the key between getting that job offer and rejection. If you can get three people to become paying subscribers to this newsletter, you win a free mock interview. This offer has no upper limit, so the more subs you can get, the more mock interviews you win.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on:

Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/

My content:

Read my articles: https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75