Java Daily Coding Problem #005

Daily Coding Problem is a website which will send you a programming challenge to your inbox every day. I want to show beginners how to solve some of these problems using Java, so this will be an ongoing series of my solutions. Feel free to pick them apart in the comments!

Problem

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.

Given this implementation of cons:

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

Implement car and cdr.

Strategy

Spoilers! Don't look below unless you want to see my solution!

---

Daily Coding Problem mainly uses Python in their prompts (at least from what I've seen so far), and so the first thing we have to do is translate this from Python to Java. The phrase:

cons(a, b) constructs a pair

...implies that cons(a, b) constructs an object, returning an instance of that object, let's call this class of objects Pair. car() and cdr(), then are methods which take a single Pair as an argument and return the first or the second value in the pair, respectively.

Python might allow a and b to be of any unspecified type, but in Java, we have to use generics or explicitly give a and b some class. Let's see if we can do this with generics.

Finally, there's a bit of a weird structure going on inside cons(a, b). Within it, we define the higher-order function pair, which takes as an argument a second function, f, which we apply to a and b (in that order), without knowing what f is ahead of time. Note that cons(a, b) doesn't return pair(f) with any particular argument passed in as f -- it returns pair, the function itself. The effect is that cons(a, b) actually returns a partially-defined function, f(a, b), where a and b are known, but f isn't.

If you run this in the Python shell, you get:

>>> def cons(a, b):
...     def pair(f):
...         return f(a,b)
...     return pair
... 
>>> cons(1, 2)
<function pair at 0x10edbd050>

Note how cons() returns a function (named pair). In Python, we can pass a defined function or a lambda to this return value:

>>> ret = cons(2, 3)
>>> ret(lambda a, b: a*b)
6
>>> ret(lambda a, b: a+b)
5
>>> def fn(a, b):
...     return a**b
... 
>>> ret(fn)
8

This behaviour will be a bit trickier to implement in Java.

Code

First, let's see if we can define this cons function in Java. cons is a method which takes two generic arguments and returns... something:

public ??? cons (T a, U b) {
 ...
}

Within cons, we have another function defined, pair, which takes a function as an argument (specifically a BiFunction and returns that function applied to the arguments supplied to the outer cons function:

public pair (BiFunction<T,U,R> f) {
  return f(a,b); // a and b defined in cons()
}

There are some problems with this, though. Firstly, you cannot define a function within a function like this in Java. Instead, we have to define this inner function in terms of functional interfaces. pair() is a function which takes a different function, f as an argument, and returns some value. That makes it a regular old Function:

Function<BiFunction<T,U,R>, R> pair = f -> f.apply(a, b);

The type signature for the inner function is <T,U,R> because we know nothing about the function f. All we know is that it takes two arguments which may be of the same or different types (T and U), and it returns a value which may be one of those types or a totally different third type (R). But when we define f and pass it to pair, f will return a value of type R, which then becomes the return value (and type) of pair. So pair's return type should also be R.

Incorporating this into cons gives:

jshell> public class DCP005<T,U,R> {
   ...>   public Function<BiFunction<T,U,R>,R> cons(T a, U b) {
   ...>     Function<BiFunction<T,U,R>,R> pair = f -> f.apply(a,b);
   ...>     return pair;
   ...>   }
   ...> }

...where the return type of cons is simply the type of pair, since that's what cons returns.

Note that this is within the jshell. We can explicitly (and very verbosely) declare all of the types like:

jshell> Function<BiFunction<Integer,Integer,Integer>,Integer> exa = (new DCP005<Integer, Integer, Integer>()).cons(2, 3)
exa ==> DCP005$$Lambda$24/85777802@4d41cee

...or, if we're happy to ignore the warnings, just:

jshell> Function exb = (new DCP005()).cons(2, 3)
|  Warning:
|  unchecked call to cons(T,U) as a member of the raw type DCP005
|  Function exb = (new DCP005()).cons(2, 3);
|                 ^-----------------------^
exb ==> DCP005$$Lambda$24/85777802@2833cc44

To apply the method, we can do:

jshell> exa.apply((x,y) -> x+y)
$28 ==> 5

jshell> exa.apply((x,y) -> x*y)
$29 ==> 6

...it's a bit clunkier with exb, but it works:

jshell> exb.apply((BiFunction)((x,y) -> (Integer)x+(Integer)y))
|  Warning:
|  unchecked call to apply(T) as a member of the raw type java.util.function.Function
|  exb.apply((BiFunction)((x,y) -> (Integer)x+(Integer)y))
|  ^-----------------------------------------------------^
$3 ==> 5

jshell> exb.apply((BiFunction)((x,y) -> (Integer)x*(Integer)y))
|  Warning:
|  unchecked call to apply(T) as a member of the raw type java.util.function.Function
|  exb.apply((BiFunction)((x,y) -> (Integer)x*(Integer)y))
|  ^-----------------------------------------------------^
$4 ==> 6

So we need class declarations somewhere, whether when we're creating the Function with cons() or when we're calling it with apply(). Now, the only thing that's still a bit awkward is how we had to call cons as a member of a DCP005 object. We can eliminate this by declaring both the class and the method as static, but we can't do that in the jshell. Instead, let's create a Maven project with only a single source file:

package DCP;

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

public class App {

  public static <T,U,R> Function<BiFunction<T,U,R>,R> cons(T a, U b) {
    Function<BiFunction<T,U,R>,R> pair = f -> f.apply(a,b);
    return pair;
  }

}

Compiling this and loading the package in jshell makes this much nicer and easier:

$ mvn package
...

$ jshell --class-path target/005-1.0-SNAPSHOT.jar
...

jshell> import static DCP.App.*

jshell> cons(2, 3).apply((x,y) -> x+y)
$4 ==> 5

jshell> cons(2, 3).apply((x,y) -> x*y)
$5 ==> 6

Now, we have nearly the same syntax that we had in Python! (I would argue more intuitive syntax, as well.) When defined and used in this way, Java will infer the types of the objects passed in:

jshell> cons(2, "3").apply((x,y) -> x)
$9 ==> 2

jshell> cons(2, "3").apply((x,y) -> x + y)
$10 ==> "23"

With the hard part out of the way, let's tackle the easy part: actually solving the prompt. For this, we just need two functions which take the return value from cons() and return either the left or the right member of the pair. Something like:

  public static <T,U> T car(Function<BiFunction<T,U,T>,T> cons) {
    return cons.apply((a,b) -> a);
  }

  public static <T,U> U cdr(Function<BiFunction<T,U,U>,U> cons) {
    return cons.apply((a,b) -> b);
  }

The generics here are tricky, but what car is saying, basically, is that the function supplied to it must take two objects of type T and U, and return an object of type T. cdr says that the function supplied to it must take two objects of type T and U, and return an object of type U.

Definitely more verbose for the programmer, but more type-safe. And the verbosity for the user (in the jshell) is precisely equal to the Python version (assuming we'd already defined car and cdr in Python, as well):

>>> car(cons(2, "3"))
2

>>> cdr(cons(2, "3"))
'3'

jshell> car(cons(2, "3"))
$2 ==> 2

jshell> cdr(cons(2, "3"))
$3 ==> "3"

The only difference is that we need to import the package we defined in Java.

Discussion

Well, that was a journey! The actual problem was super easy. If I would have used Python only, it would have been solved in minutes. But I want to solve these coding problems with Java, which means that sometimes I need to translate code across languages. Usually it's not too bad, but today it was a bit tricky with the generic types involved. I definitely learned something while solving this prompt, and I hope you did, too!

---

All the code for my Daily Coding Problems solutions is available at github.com/awwsmm/daily.

Suggestions? Let me know in the comments.

Comments

[Erik Pischel]

What about type inference in your example exa and exb?

The given definition of cons is really surprising since cons, car and cdr are basic functions in LISP and in LISP cons is just constructing a 2-element list.

[Jonathan Kuhl]

I'm not sure I fully understood what the question was asking, but I ended up with this:

// main.java:

package com.company;

public class Main {

    public static void main(String[] args) {
        Pair<Integer> p = Pair.cons(3,4);
        System.out.println("The pair is: " + p);
        Integer a = Pair.car(p);
        System.out.println("Output of Pair.car(): " + a);
        Integer b = Pair.cdr(p);
        System.out.println("Output of Pair.cdr(): " + b);
    }
}

// Pair.java

package com.company;

public class Pair<T> {

    private T a;
    private T b;

    public Pair(T a, T b) {
        this.a = a;
        this.b = b;
    }

    public static <T> Pair<T> cons(T a, T b) {
        return new Pair<T>(a, b);
    }

    public static <T> T car(Pair p) {
        return (T)p.a;
    }

    public static <T> T cdr(Pair p) {
        return (T)p.b;
    }

    @Override
    public String toString() {
        return "(" + a + "," + b + ")";
    }
}

The cons function seemed redundant with the constructor but I implemented it anyways. Had to do some research in implementing generic static methods.

[Andrew (he/him)]

Yeah, see this is what I think the question implies, but it's not actually what the example Python code does. The Python code given, if followed, makes the problem needlessly complex. My first instinct was to do something like your solution, but I ended up trying to stick as closely to the prompt as possible, and that includes returning a partially-defined function from const.

Some notes on yours:

Defining Pair<T> with only one generic type means that a and b must be the same type. They can't be Integer and Double, for instance. Maybe try expanding it so a and b can have independent types?

Your return statements from cdr() and car() have explicit type-casting:

        return (T)p.b;

...if you instead declare the type of Pair in the argument, you can avoid this. Instead of:

    public static <T> T cdr(Pair p) {
        return (T)p.b;
    }

...write:

    public static <T> T cdr(Pair<T> p) {
        return p.b;
    }

Also, I think you can drop the <T> in the methods, since you already declare T in the class signature:

    public static T cdr(Pair<T> p) {
        return p.b;
    }

Other than that, that's basically what I would have written, if we needed to make a Pair class. Nice work!