Typing a technical interview

I offer the readers of "Habrakhabr" a translation of an article by Kyle Kingsbury, aka "Aphyr".
Previously: Enchanting Technical Interview

In the old days, long before the rise of the Church, all spells were pronounced on a pure occasion, all actions were allowed, and death was common. Many witches have cured because of their magic, they were found broken in the center of a circle of twisted, glazed trees and burning stones that did not fade even under water; some disappeared completely, or began to travel through the mountain passes, never touching the ground with their feet, never warming the air with their breath.

As a child, you heard the story of Gulveig-then-Khyor, who was resurrected three times from the fire of the judgment, who traveled the world, making a seidr - reading and re-interweaving the future. Her predictions (and there were many of them) became famous — they were repeated even by those who walk abroad — but history has changed her survival. In an ecstatic trance seidr, she foresaw her future, and conquered death. Her spells never broke, and she became a friend to expelled women, the ancestors of your kind. It is said that Odin himself learned the immortality from her.

To this day, all the witches are indebted to Khyor. Few dive into ancient, unstructured magic in our day. The languages ​​themselves, in which the spells are written, are stabilized by the seidr itself in its structure, passing the evoked energy along safe paths - to a greater or lesser extent. Of course, occasional explosions sometimes occur. But for the most part they are from the variety of burning eyebrows, rather than creating new fjords of interesting outlines.

"All is well?"

The interviewer - Chris, judging by the name on the badge - is quite young, which corresponds to the custom of the Valley. He wears a sweatshirt, which, judging by the lack of trademarks, costs at least a hundred and three dollars. He does not resemble any animal at all that makes you think. Usually these things are easy for you.

“You mean at all? I don’t think,” you look around the conference room, as if looking for confirmation. The walls smell like conflict avoidance and Slack messages.

"Well, uh, well. Yes, you are probably right." his voice sounds shy. "But still, I would like to do a little exercise. A simple programmer problem so that I can understand how you solve problems."

Once you solved the problem with a knife made from a piece of obsidian. You are wondering if Chris has the strength to repeat what you did.

"Taak ... this task is called N-Queens, and it is quite simple. With a chessboard of NxN size, you need to find a way to safely place N queens on this board."

You draw an ordinary, eight-by-eight chess field on a white wallboard, and carefully place a group of eight queens in the center. They stand in a tight circle to speak with each other as equals.

"Uh, no - this is wrong. See? This queen can cut down any of these four with one move."

"You really are not able to," - you ask in a voice that is cold as a stone, - "to imagine eight powerful women in one room who do not want to kill each other?"

"Uh ... this is just a problem statement."

Perhaps this is the matriarchs of the warring clans. They gathered to discuss the truce - but none of them trusts the other if she can reach out with a dagger. This also happened in the history of your kind.

"Can I use any language?"

"Of course."

Act quickly until he understands his mistake.

{-# OPTIONS_GHC -fno-warn-missing-methods #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-} 

"Ah, this is Haskell! I taught him at the college!" He pauses and snorts. "Undecidable instances?"

"We have to use it," you happily inform him, "because Hask is not a category."

“Oh, right,” Chris gives his unfinished opinion to no one in particular. "So we used to think in Haskell subsets, where types had no lower values."

“It’s possible,” you agree, but too quietly for Chris to hear you, while being completely sure of the opposite.

 nil = undefined 

Now there will be an awkward question. We must reject it, issuing the first thing that comes to mind. "To keep our queen positions, we need a linked list, right?"

"Of course, or vector."

"Lists are easier."

"OK, well, use what you prefer."

Calling a coherent list from void. That floats on the surface of the screen: a classic structure, expressed in a thousand ways, but always beautiful. You sigh with satisfaction.

 data Nil data Cons x xs 

"And was it possible to use the built-in lists?" - asks Chris, whose eyebrow is crawling up.

"What?" - you have no idea what he is talking about. "Oh, no - then we have to drag the entire library here. It's easier to identify them inside."

 class First list x | list -> x instance First Nil Nil instance First (Cons x more) x 

"The 'class' keyword defines the function signature" - you remind Chris, who sort of forgot something. "First accepts the list and returns the x value from it. The function has two instances — Haskell uses pattern matching to select which call. First from the list Nil returns Nil, and First from the Cons cell returns the value of the cell, x."

You allow what has been said to be absorbed, and you go on to sticking lists.

 class ListConcat abc | ab -> c instance ListConcat Nil xx instance (ListConcat as bs cs) => ListConcat (Cons a as) bs (Cons a cs) 

"And what's the arrow?" - asks Chris. Tell him that it means implication. "To get ListConcat after the arrow, we need ListConcat before the arrow."

Understanding dawns. "A. is correct! This is a recursion because ListConcat appears on both sides. And the definition with Nil is the base case."

"Exactly". You're so proud of Chris. He is keeping pace. "And this is a generalized case where we want to stick together a list of lists."

 -- Concatenate all lists in a list class ListConcatAll ls l | ls -> l instance ListConcatAll Nil Nil instance (ListConcat chunk acc result, ListConcatAll rest acc) => ListConcatAll (Cons chunk rest) result -- Is any element of this list True? class AnyTrue list t | list -> t instance AnyTrue Nil False instance AnyTrue (Cons True more) True instance (AnyTrue list t) => AnyTrue (Cons False list) t 

This required more concentration than you liked, so we retreat to something simpler. “Let's do some boolean values,” you suggest in the tone that people usually invite to dinner.

"What for?"

"Because we need them, of course"

You grab two meaningless constants from emptiness, and fill them with meaning.

 data True data False class Not b1 b | b1 -> b instance Not False True instance Not True False class Or b1 b2 b | b1 b2 -> b instance Or True True True instance Or True False True instance Or False True True instance Or False False False 

Freya will probably rejoice. The birth of algebra into the world is a wonderful event.

"And I suppose that we also need integral numbers to store the coordinates of our queens," you mutter. "We work exclusively in positive coordinates, so the usual Peano construction will suffice." You pull the hair out of your hair and tie a knot for zero on it.

 data Z data S n type N0 = Z type N1 = S N0 type N2 = S N1 type N3 = S N2 type N4 = S N3 type N5 = S N4 type N6 = S N5 type N7 = S N6 type N8 = S N7 

"Do you ... define natural numbers manually? Why?"

"Haskell is for mathematicians," you explain, "We always define our terms."

 -- Equality class PeanoEqual abt | ab -> t instance PeanoEqual ZZ True instance PeanoEqual (S a) Z False instance PeanoEqual Z (S b) False instance (PeanoEqual abt) => PeanoEqual (S a) (S b) t -- Comparison (<) class PeanoLT abt | ab -> t instance PeanoLT ZZ False instance PeanoLT (S x) Z False instance PeanoLT Z (S x) True instance (PeanoLT abt) => PeanoLT (S a) (S b) t -- Absolute difference class PeanoAbsDiff abc | ab -> c instance PeanoAbsDiff ZZZ instance PeanoAbsDiff Z (S b) (S b) instance PeanoAbsDiff (S a) Z (S a) instance (PeanoAbsDiff abc) => PeanoAbsDiff (S a) (S b) c -- Integers from n to 0 class Range n xs | n -> xs instance Range Z Nil instance (Range n xs) => Range (S n) (Cons n xs) 

“Wait, wait,” Chris interrupts. "And isn't it ... isn't it necessary to have a type declaration here? Well, at least for functions?"

You are cute smile. "Haskell dynamically typed, interpreted language".

Chris looks like he swallowed a frog.

"Look, I'll show it. Let's check if one equals one."

 class LegalCompare t | -> t where legalCompare :: t instance (PeanoEqual (SZ) (SZ) t) => LegalCompare t *Main> :type legalCompare legalCompare :: True 

"See? LegalCompare is True. Now let's try to write an expression that makes an incorrect comparison. For example, let's compare True and List?"

 class IllegalCompare t | -> t where illegalCompare :: t instance (PeanoEqual True (Cons Z False) t) => IllegalCompare t 

"See? It loads perfectly. It will break only when we try to execute the expression - remember, Haskell is lazy, after all."

 *Main> :type illegalCompare illegalCompare :: PeanoEqual True (Cons Z False) t => t 

"Here you are! Type error in runtime."

"But nothing is written about the error ..."

"Well, you know. Haskell error messages are widely known for their complexity to understand."

Chris looks pretty sick. Take the opportunity to go to higher order functions.

"By an unfortunate coincidence, Haskell has no currying, so we will have to create our own tools for the partial application of functions. Here is the signature for a generalized one-ary application of the function."

 class Apply far | fa -> r 

"Just the function f, which accepts input a and returns r", the melody of variable names sounds almost like a song. "For partial applications, we could define data types like Partial1, Partial2, and so on, but since we only need some of them, it’s easier to define strictly curried versions of the functions we need. For example, like this!"

 data Conj1 list instance Apply (Conj1 list) x (Cons x list) 

Inhale deeply and let your spirit soar from these particular forms to the radiant heights of higher order functions.

 -- Map f over a list class Map f xs ys | f xs -> ys instance Map f Nil Nil instance (Apply fxy, Map f xs ys) => Map f (Cons x xs) (Cons y ys) -- Map f over list and concatenate results together class MapCat f xs zs | f xs -> zs instance MapCat f Nil Nil instance (Map f xs chunks, ListConcatAll chunks ys) => MapCat f xs ys -- Filter a list with an Apply-able predicate function class AppendIf pred x ys zs | pred x ys -> zs instance AppendIf True x ys (Cons x ys) instance AppendIf False x ys ys class Filter f xs ys | f xs -> ys instance Filter f Nil Nil instance (Apply fxt, Filter f xs ys, AppendIf tx ys zs) => Filter f (Cons x xs) zs 

For a moment, we must return to the world of specific values. Chris is still there, at least physically. The screen of your laptop has turned into a luxurious mess of purple tones due to extreme cold, but the code is still visible in its depths. The screen reminds you of a frozen lake at dusk. Liquid crystal

"Chris. Chris." He blinks quickly, as if from darkness to the light. Beautiful eyes. You remember the times when your own eyes still had color. "We are ready."

"Yes OK."

"A queen is defined by her two coordinates on the board: x and y. We will also create a partially used constructor to put queens on a given x coordinate."

 data Queen xy data Queen1 x instance Apply (Queen1 x) y (Queen xy) -- A list of queens in row x with y from 0 to n. class QueensInRow nx queens | nx -> queens instance (Range n ys, Map (Queen1 x) ys queens) => QueensInRow nx queens 

"Yes, queens!" - you mutter. This is unfortunately not the kind of interview.

Each queen can strike eight directions. You always thought it was a metaphor.

 -- Does queen a threaten queen b? class Threatens abt | ab -> t instance (PeanoEqual ax bx xeq, PeanoEqual ay by yeq, Or xeq yeq xyeq, PeanoAbsDiff ax bx dx, PeanoAbsDiff ay by dy, PeanoEqual dx dy deq, Or xyeq deq res) => Threatens (Queen ax ay) (Queen bx by) res -- Partial application of Threatens data Threatens1 a instance (Threatens abt) => Apply (Threatens1 a) bt 

A new queen appears in the room, aiming for a position. She is keenly following her colleagues, remaining out of reach. Where does she need to get up? You imagine a pack of universes — alternate worlds, each of which contains queens in different positions.

 -- Is queen b compatible with all queen as? class Safe config queen t | config queen -> t instance (Map (Threatens1 queen) config m1, AnyTrue m1 t1, Not t1 t2) => Safe config queen t2 data Safe1 config instance (Safe config queen t) => Apply (Safe1 config) queen t -- Add a queen with the given x coordinate to a legal configuration, returning -- a set of legal configurations. class AddQueen nxc cs | nxc -> cs instance (QueensInRow nx candidates, Filter (Safe1 c) candidates filtered, Map (Conj1 c) filtered cs) => AddQueen nxc cs data AddQueen2 nx instance (AddQueen nxc cs) => Apply (AddQueen2 nx) c cs -- Add a queen at x to every configuration, returning a set of legal -- configurations. class AddQueenToAll nx cs cs' | nx cs -> cs' instance (MapCat (AddQueen2 nx) cs cs') => AddQueenToAll nx cs cs' 

"And now we are entering into recursion," you whisper, turning the spell bound by the controlling thread to itself. One queen per row, in each valid position, for each configuration. Do you have any idea how the “about us” page could look like on their startup website?

 -- Add queens recursively class AddQueensIf pred nx cs cs' | pred nx cs -> cs' instance AddQueensIf False nx cs cs instance (AddQueenToAll nx cs cs2, AddQueens n (S x) cs2 cs') => AddQueensIf True nx cs cs' class AddQueens nx cs cs' | nx cs -> cs' instance (PeanoLT xn pred, AddQueensIf pred nx cs cs') => AddQueens nx cs cs' -- Solve class Solution nc | n -> c where solution :: n -> c instance (AddQueens n Z (Cons Nil Nil) cs, First cs c) => Solution nc where solution = nil 

Chris habitually looks through everything, like a man who has experienced a terrible loss or, perhaps, witnessed a close explosion. Gently take him by the shoulder. "Psst!", - you whisper, - "Everything is ready, the decision is close."

 *Main> :type solution (nil :: N6) solution (nil :: N6) :: Cons (Queen (S (S (S (S (SZ))))) (SZ)) (Cons (Queen (S (S (S (SZ)))) (S (S (SZ)))) (Cons (Queen (S (S (SZ))) (S (S (S (S (SZ)))))) (Cons (Queen (S (SZ)) Z) (Cons (Queen (SZ) (S (SZ))) (Cons (Queen Z (S (S (S (SZ))))) Nil))))) 

Look, the beautiful output put the output exactly like this, creating a lovely line of zeros along the vertical axis. "So, we have queens by 5.1, by 4.3, by 3, 5, by 2.0, 1.2, and 0.4. Come, Chris?"

Chris has been staring at you for a very, very long time. "You never ... never wrote the real meaning. You ... you understand that the type system must contain values, right?"

"No," you inform him, as Deputy Captain Obvious. "No, it is not."

He leans back in his chair so far that you think that he is about to turn over, and then rubs his face with both hands. You, already seeing through the seidr email with a refusal, you know what it is going to say.

"We will contact you."

With sincere thanks to Patrick Thompson and Type Level Insanity Conrad Parker.