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.

## Top comments (3)

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

The

`cons`

function seemed redundant with the constructor but I implemented it anyways. Had to do some research in implementing generic static methods.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`

mustbe 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:...if you instead declare the type of

`Pair`

in the argument, you can avoid this. Instead of:...write:

Also, I think you can drop the

`<T>`

in the methods, since you already declare`T`

in the class signature:Other than that, that's basically what I would have written, if we needed to make a

`Pair`

class. Nice work!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.