Construct and Deconstruct a Pair

Problem Statement (Asked By Jane Street)

The function cons(a, b) creates a pair of two elements. Implement two functions:

  1. car(pair): Extracts the first element of the pair.
  2. cdr(pair): Extracts the second element of the pair.

For instance:

  • car(cons(3, 4)) should return 3.
  • cdr(cons(3, 4)) should return 4.

Below is the implementation of cons:

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

Your task is to define the car and cdr functions.

Disclaimer: Try solving the problem on your own first! Use this solution only as a reference to learn and improve.


Solution:

This is a fascinating example of using closures to encapsulate and manage data. The key lies in understanding how cons, car, and cdr interact.

The cons function takes two arguments, a and b, and returns an anonymous function that takes another function f as its input. This function f is then invoked with a and b. This means the output of cons is a callable function that “stores” a and b implicitly through its closure.

To retrieve a (the first element) or b (the second element), we pass a specific function to the pair. For car, this function extracts the first parameter; for cdr, it extracts the second parameter.

Here’s how you can implement this idea in Java:

import java.util.function.BiFunction;
import java.util.function.Function;

public class ConsExample {

    // Cons function: creates a pair
    public static <A, B> Function<BiFunction<A, B, ?>, ?> cons(A a, B b) {
        return (BiFunction<A, B, ?> f) -> f.apply(a, b);
    }

    // Car function: retrieves the first element
    public static <A, B> A car(Function<BiFunction<A, B, ?>, ?> pair) {
        return (A) pair.apply((a, b) -> a);
    }

    // Cdr function: retrieves the second element
    public static <A, B> B cdr(Function<BiFunction<A, B, ?>, ?> pair) {
        return (B) pair.apply((a, b) -> b);
    }

    public static void main(String[] args) {
        // Example usage
        Function<BiFunction<Integer, String, ?>, ?> pair = cons(42, "Hello");

        // Retrieve the first and second elements
        int first = car(pair);
        String second = cdr(pair);

        System.out.println("First: " + first);  // Output: First: 42
        System.out.println("Second: " + second); // Output: Second: Hello
    }
}

Explanation:

  1. cons Function:
    • Creates a closure by capturing the values a and b.
    • Returns a function that takes a BiFunction and applies it to a and b.
  2. car Function:
    • Extracts the first element by applying a lambda function (a, b) -> a to the pair.
  3. cdr Function:
    • Extracts the second element by applying a lambda function (a, b) -> b to the pair.

Fun Fact:

In Lisp, cdr is pronounced “cudder,” as a nod to its roots in the language’s historical implementation details.

This Java implementation mirrors the functional behavior of the original Python example and demonstrates how closures can be effectively used to encapsulate and retrieve data.


Did this solution help you understand the concept better? Let me know your thoughts in the comments below! Don’t forget to follow us on Instagram @coderz.py for more DSA tips and solutions to ace your coding interviews.

Recent Posts

Longest Absolute Path in File System Representation

Find the length of the longest absolute path to a file within the abstracted file…

3 days ago

Efficient Order Log Storage

You manage an e-commerce website and need to keep track of the last N order…

2 weeks ago

Select a Random Element from a Stream

You are given a stream of elements that is too large to fit into memory.…

3 weeks ago

Estimate π Using Monte Carlo Method

The formula for the area of a circle is given by πr². Use the Monte…

1 month ago

Longest Substring with K Distinct Characters

Given an integer k and a string s, write a function to determine the length…

1 month ago

Staircase Climbing Ways

There is a staircase with N steps, and you can ascend either 1 step or…

1 month ago