DEV Community

Let the compiler do the work for you!

Jan van Brügge on August 01, 2019

Recently I came across a little programming puzzle, the task was to take a binary search tree and return a new tree, where every node is replaced b...
Collapse
 
jvanbruegge profile image
Jan van Brügge • Edited

The problem is that Java's type system is not able to express these powerful abstractions. I've added the code for mapAccumR to the article. You can see that it requires any traversable t and later as third argument is t b meaning this traversable t contains a b, whatever that might be. In Java terms: t is Generic, kinda like <T extends Traversable>, the problem is the B. You cannot have generic generics in Java (also called higher-order types).

mapAccumR<T extends Traversable, B>(/* ... */, T<B> x)

is not valid Java

 
shikasd profile image
Andrei Shikov

Arrow-kt implement support of higher kinded types for Kotlin (which has a similar limitation). They create a type using generic Kind<T, B> and some tools to convert it to usable Kotlin type.

Suggest you to check it out!

Collapse
 
nestedsoftware profile image
Nested Software

minor correction: JavaScript has Array.reduce, not fold.

Also, it seems to me that it would be helpful to explain mapAccumR, since that is doing the real heavy lifting here. Presumably you could implement that in Java (or maybe there is a library that does it already) and the solutions would become more or less the same.

Collapse
 
jvanbruegge profile image
Jan van Brügge

Yes, fixed the Array.reduce

The nice thing is, mapAccumR is not doing much either. It relies completely on the power of Traversable the class that the compiler generated for us. If you would change the type signature of solve to allow for other Traversables than Tree, the code would work without any changes also for lists or arrays for example. All thanks to the power of fundamental abstractions.
I've added a short paragraph that shows that mapAccumR is not a lot of code.

Collapse
 
drbearhands profile image
DrBearhands

Maybe it would help clear the confusion by mentioning that deriving creates functions with certain rules (map, fold, etc.) that operate on the types?

Collapse
 
drbearhands profile image
DrBearhands

I've been having doubts about the use of deriving when it comes to code style. It sure as hell is convenient but it hides information from the programmer. It would cause problems for instance if for some reason someone were to switch the order of left and right branches (ignoring why the hell someone would do that). Admittedly this is also an argument for records.

For Aeson in particular I'd just rather resort to declaring my own instances.

What are your thoughts on this issue?

Collapse
 
jvanbruegge profile image
Jan van Brügge

I really advocate the use of deriving as much is possible. DervingVia basically allows you to create a standard set of instances you can derive for other data types. Handwritten instances should IMO be kept as small as possible.
As said, more code always means more bugs and it makes the code harder to read. The derived instances always behave the same, so it is independent of local conventions. Also, due to the laws attached to the classes, most of the time, there is only one lawful instance for a given datatype

Collapse
 
josephthecoder profile image
Joseph Stevens

How that is way cleaner! Let the computer do it I say