Java Daily Coding Problem #005
Tags: java, challenge, beginners, dailycodingproblem
Published: 2019-06-20 19:11:40

[Daily Coding Problem](https://dailycodingproblem.com/) 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:

```python
>>> 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:

```python
>>> 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:

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

Within `cons`, we have another function defined, `pair`, which takes a [`function`](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/function/package-summary.html) as an argument (specifically a [`BiFunction`](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/function/BiFunction.html) and returns that function applied to the arguments supplied to the outer `cons` function:

```java
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](https://stackoverflow.com/a/7097287/2925434). 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`](https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/function/Function.html):

```java
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:

```java
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:

```java
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:

```java
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:

```java
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:

```java
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:

```java
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:

```java
$ 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:

```java
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:

```java
  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):

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

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

```java
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](https://github.com/awwsmm/daily).

Suggestions? Let me know in the comments.