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... [Read Full]
markdown guide

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.


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.


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


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?


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


Wow, that's cool!
You should consider making this a library for java!


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


Well, challenge accepted. I shall find a work around!
Wish me luck!

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!


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

code of conduct - report abuse