Typing the technical interview in Scala
In the beginning, long before the rise of the great Serpent Java, there existed a world filled only with the purest of creatures. They were bounded only by types carved in their chains by their creators. They could move between streams without fear of affecting each other and only collaborate when the types they were woven with allowed it.
Although for some, this life felt pointless as if it did not have any effect . So some of the creatures filled with rage cast their shackles and morphed in the runtime. By doing so, corrupting and changing the world around them without any thought.
Many millennia later, when the world was corrupt beyond recognition Alonzo Church, Haskell Curry, William Alvin Howard and many sorcerers of their kind, stepped forth and enlightened the world with the greatest gift called Typed Lambda Calculus.
The Arcane Mage
So our story beings here, where a young Typing Sorcerer enters the manor of a neighbouring guild of developers, that are trying to grow there ranks. He was welcomed by a senior Warlock and asked if he wants a pint of tee or ale before the trials. He pleasantly refuses and moves towards a room, resembling a glass cage.
In the room, he sits down on the first chair he finds and waits for the Senior Warlock provide him with a challenge. The Warlock eagerly provides the first assignment that is to write a scroll of code that would summon the result of any Factorial . He also adds that the young Sorcerer can use any magic that he sees fit.
Without hesitation, the young Scholar of the art of Types puts a mantra for any natural number:
The Warlock squints, but before he can formulate a question, the young sorcerer provides ways to getSum and Product of these numbers by using Auxiliar types to show dependent relation of these computations:
He goes so far as to express the Prod of the types in using his previously defined Sum
By having Prod definition for all natural numbers the young sorcerer can now summon a Typed versioned of Factorial :
These are not simple mutation spells that the Warlock is familiar with. He gets puzzled, but after trying to use the scroll on incantation Factorial[_4].value he is pleasantly surprised.
The Trial of FizzBuzz
The Warlock was amused but puzzled. Why did the young sorcerer use such Arcane magic, why not just mutate state in a for Incantation. Young scholar saw the puzzled look on the warlock's face and explained that incantation like this was used to slay Compiler Dragons in his old village of Idris.
The Warlock recognised some symbols in the scroll of magic that reminded him of incantations seen in the neighbouring Haskell village that was protected from mutations and the only way to enter it was by uttering the Monad spell.
As the last chant, the warlock asked to summon the great list of fizzBuzz , where numbers divisible by three would transform to Fizz , by five would change to Buzz and by both would convert to FizzBuzz . It seemed that the description of the spell implied mutation, but the young sorcerer did not hesitate and started typing more inductive definitions:
To summon a portal between Type and Value worlds ToInt incantation was used:
When the portal opened in front of Warlock’s eyes, his heart started pounding and hoping this is not some sort of Necromancer in disguise opening a portal to his crypt.
Young Sorcerer did not even look what’s happening around them while writing the types for FizzBuzz :
and finally summoning the scroll of rules:
The Warlock read threw and noticed that there is no chant for the List of FizzBuzz ‘es and asked to write that as well.
After typing FizzBuzzResult[_16] the REPL returned the expected value. That left the Senior Warlock confused and puzzled questioning the methods of the young one. It seems he did not yet learn that types are used for constrains not for writing programs in them.
Conclusion
After all the type <-> value portals where closed. The Warlock shook the young Sorcerers hand and uttered: “We’ll be in touch.”.
References
- This post was inspired by Typing The Technical Interview
- Most of the code was sourced and inspired by Shapeless. Huge thanks to all of its contributors that provided examples.
- All the code can be found here: https://gist.github.com/Algiras/81dd88112f7a284883d379c2977aa3a1
