## DEV Community is a community of 848,284 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Andrew (he/him)

Posted on • Updated on

# 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.

## Discussion (3)

Jonathan Kuhl • Edited on

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) • Edited on

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!

Erik Pischel