[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.
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.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.