Typing the technical interview | Hacker News Reader

Typing the technical interview

aphyr.com

413 pointszorpner80 comments

The previous two of these were also great:

https://aphyr.com/posts/340-reversing-the-technical-intervie...

https://aphyr.com/posts/341-hexing-the-technical-interview

   “You’re… defining the natural numbers by hand? Why?”

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

That's just beautiful

How.. beautiful.

Like I said earlier in the "half-dead chicken thread", the occult is a quiet and powerful force in computer science and related areas. With things like neural networks and learning functions, we're approaching the ultimate.

In this case, it was only a handful of lines of a functional language that could solve the N-Queens problem.. Of course, mixed with a bit of Lovecraftian lore and Norse magic.

It's only a careful look beneath the stolid atheism and antitheism that the tech community likes to front.. All is not as it appears just beneath the digital waves, is it?

An Italian I used to work with maintained a small shrine to Ada Lovelace on his desk.

I always like to kindly remind people that sufficiently-advanced magic is indistinguishable from technology.

My favourite casting of this is 'any technology distinguishable from magic is insufficiently advanced'.

"Any sufficiently advanced technology is insufficiently documented."

[I think I coined this one, back in the day. But I was probably preceded by someone even more damaged]

And then we come full circle back to heavy wizardry https://en.wikipedia.org/wiki/Magic_(programming)#Variants

Remember that computing is a quick way to invoke CASE NIGHTMARE GREEN.

Take your chintzy superstitions elsewhere, smug smug.

Is this an HN novelty account in the making?

That wasn't my original intent, no. I already have a HN account with a few thousand karma. What I needed was to be able to comment without tying it to my main username.

I feel a bit silly pointing this out, but all that stuff about hexes and witches and everything mystical in the article is just a playful framing story. Aphyr in all likelihood is not an occultist or mystic, and is just writing playfully (and somewhat ironically) about technology and modern interviews. The playful conflation of mystical incantations and writing code is an old hacker tradition (other playful traditions: mixing buddhism and zen with coding, and writing apocryphal parables about it). Also, it should be noted that being an atheist doesn't preclude being interested in the history of religion, folklore literature and traditions, or even entirely fictional religions.

Of course, maybe your comment above was playful and ironic as well, in which case I missed the point :)

This is awesome. I didn't even really see what was happening until it was too late.

If you enjoyed that you might enjoy the structure of the proof of the complexity of type inference for \-calculus: http://www.cs.brandeis.edu/~mairson/Papers/jfp02.pdf . They construct arbitrary boolean circuits from simple types and evaluate the circuits through type checking.

Not sure if you noticed but your username fits the mythological setting :)

So where can I buy my "Summon a linked list from the void" T-shirt?

Aphyr is a legend. I would buy one of these shirts too.

Someone, please design this. Then post a link. I will be your first customer

It's like the HN generation's "I put on my robe and wizard hat"

    You smile kindly. “Haskell is a dynamically-typed, interpreted language.”

Thou shalt not suffer a witch to live!

> Summon a linked list from the void. It floats to the surface of the screen: a timeless structure, expressed a thousand ways, but always beautiful.

Coincidentally, I had Bach's E minor organ sonata on in the background, so...

> You sigh contentedly.

I did, I started smiling from ear as soon as I read the now-classic "Summon a ______ from the void". :)

Also, TIL: https://en.wikipedia.org/wiki/Sei%C3%B0r

Nope.

This is a polemic against people who don't know Haskell. Previous iterations were the same except Clojure/Lisp.

Aphyr/Kyle is a genius, and one of my favorite people on the internet. But this series is the WRONG way to attack the code interview, which deserves to be attacked, BUT.

Some of us face real challenges about how to find common ground with interviewees. Because you know you're smarter than those questions is not a reason to discount them.

I will sacrifice ALL my HN points to say this is bullshit. Bullshit written in decent prose, but still bullshit.

I doubt Aphyr/Kyle is one of those people who would know how to simultaneously rotate five binary trees using only one pointer off the top of his head (or whatever). The point of this series isn't that it's an attack on people who aren't comfortable with Haskell type magic (or the extremes of Lisp or JVM classloader-fu): whatever made you think that?

Now if you mean that making fun of the coding interview itself is wrong because there exist people who either interview people for a living or people who are job-hunting right now, and this makes light of their troubles, well, that's different. I disagree, but it's still more sensible than "lol you dont know Haskal, nub".

I really didn't read this as an attack or polemic on code interviews. It's just a fun parody. Like how the TV show Silicon Valley some times pokes fun at actual Silicon Valley, but isn't an attack on it.

It is not only a fun parody; it also lightheartedly demonstrates a useful type-level programming technique. It is not obvious how to use functional dependencies to write code like that and before type families came along it was the only option. The problem is a toy problem but the technique is serious

"One queen per row, in every legal position, for every configuration. You imagine what their startup’s about-us page would look like."

the coups de grâce!!!

> Seize two meaningless constants from the void, and imbue them with meaning.

Holy shit

This is, literally, math.

For the N queens on an NxN chess board, wouldn't you put them in a fibonaci spiral? Of course I can draw the board and explain it, but I have no idea how show that fibonaci formula modified for a chess board. Do you think that would be enough?

People like Criss who ask this question in interviews are looking for a brute force solution with recursive backtracking.

Is that not what's happening here? Except GHC has the recursive backtracking built in? The code looks a lot like the equivalent Prolog implementation.

I think you're supposed to show that you know how to do that yourself, instead of just using an existing implementation.

Though I don't think I would use backtracking for an actual haskell solution. Probably something like:

    import Data.List (permutations)

    solve :: Int -> [[Int]]
    solve i = filter (valid . zip [1..]) (permutations [1..i])

    valid :: [(Int, Int)] -> Bool
    valid [] = True
    valid (x:xs) = singleValid x xs && valid xs
      where
        singleValid x xs = all (pairwiseValid x) xs
        pairwiseValid (x1, y1) (x2, y2) = abs (x1-x2) /= abs (y1-y2)

I'm a fan of the min-conflicts heuristic for this problem. See eg section 5.3 of http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf

This is decent prolog code ;)

Any sophisticated enough type system contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Prolog.

It's quite formally specified.

Seems to not be very bug-ridden either. But maybe somebody should code a non-backtracking operator extension for GHC. This way, next time he could claim Haskell is a dynamically typed, interpreted, lazy and not-pure language.

> It's quite formally specified.

Haha, that's a good one. Haskell, unlike SML, is _not_ formally specified. If only, if only... sobs

Way to cut to the conclusion:)

I do think datalog semantics composes way nicer than prolog though.

I think some of the type class stuff was formalized in the papers on HM(X) , though the combination of extensions in this post hasn't. But perhaps should be on the table for formalization.

This is the Old type art. It's tragic to see such unkind typing.

I honestly have no idea what's going on, but his writing is humorous.

As far as I can tell, this is an article teaching functional programmers LISP, using the framing of a LISP programmer who trolls a technical interviewer by writing LISP-like Haskell libraries with which to solve the n-queens problem.

I'm not a Haskell expert (and I skimmed the article), but I believe the article is about designing a simple method of computation that runs on top of Haskell's type system and that operates via type inference.

The answer at the end is evaluated by asking Haskell to print out the type of the variable "solution", and the answer is encoded within that variable's type (rather than its value).

In Aphyr's meta-language, "values" are represented by Haskell types, "functions" are represented by Haskell type constructors (functions from types to other types), and "computation" is represented by type inference.

For example, a cons cell in a typical language is a data structure consisting of two elements, so in Aphyr's meta-language it's represented as the binary type constructor `data Cons x xs`.

The meta-language also defines its own natural numbers and arithmetic in the fashion of Peano arithmetic. `data Z` declares a type that will represent the zero value, and `data S n` declares a unary type constructor representing the successor function. For example, zero is the type `Z`, one is the type `S Z` ("the successor to zero"), two is the type `S (S Z)` ("the successor to the successor to zero"), etc. Using this construction we can build arithmetic recursively. For example, equality in Peano arithmetic is implemented in Aphyr's program as:

  class PeanoEqual a b t | a b -> t
  instance PeanoEqual Z     Z     True
  instance PeanoEqual (S a) Z     False
  instance PeanoEqual Z     (S b) False
  instance (PeanoEqual a b t)
    => PeanoEqual (S a) (S b) t

You can read that code as if it approximately means the following (pseudo-code, bit hand-wavy):

  function PeanoEqual a b 
  PeanoEqual(0,    0) = True
  PeanoEqual(a+1,  0) = False
  PeanoEqual(0,  b+1) = False
  PeanoEqual(a,    b) =    # a and b are both nonzero
     PeanoEqual(a-1, b-1)  # so recurse

My pseudo-code expresses equality of natural numbers by recursively subtracting 1 (that is, undoing our successor function) from `a` and `b` until one of the values is zero. If both are zero, then the original inputs were equal; otherwise they were unequal. In the Haskell meta-program, we don't have imperative recursion, but have recursive types and subtype relationships, and unification that understands them and will construct those types.

Further reading:

https://wiki.haskell.org/Constructor#Type_constructor

https://en.wikipedia.org/wiki/Kind_(type_theory)

https://en.wikipedia.org/wiki/Peano_axioms

Yes, and that functional language is LISP, as demonstrated by the parentheses and Cons operator, and a few other things I probably didn't catch. I suppose it's less educational, and more just a meta-level trolling.

I don't think it's actually Lisp. Lisp is essentially an imperative language; you use functional concepts, but you're telling the computer what concrete thing to do at each step. This is just asking it to resolve types in a type system, using whatever algorithm it likes to satisfy the type constraints.

Note, in particular, the complete lack of algorithm to solve the actual n-queens problem: just the constraints.

Fair enough, I pretty much nope'd out after the "Haskell is a dynamically-typed, interpreted language" bit, scrolled to the end, and saw some LISP-y output.

Cons is not exclusively a Lisp operation, Haskell's lists (among other languages) are implemented with cons: [1,2] is syntactic sugar for 1:2:(). And the parens are also part of the Haskell syntax, not something added to make it look like Lisp - note the lack of parens around the outermost types.

If anything it seems closest to Idris, given the Peano arithmetic...

  PeanoEqual(a,    b) =    # a and b are both nonzero
     PeanoEqual(a-1, b-1)  # so recurse

Subtracting Peano literals would involve some constraints in the type, so shouldn't that be (a+1,b+1) for typing purposes?

This is closer to using the type system to simulate something Prolog-like, where typeclass membership is like a predicate.

I knew that ListConcat looked fishy.

Here's what's going on, as far as I can tell:

A "class" in Haskell is a typeclass, sort of like a trait in Rust or an interface / abstract class in OO languages. An "instance" is a specific data type that satisfies the rules of the typeclass. The classic example is something like this:

    class Eq a where 
      (==)     :: a -> a -> Bool

    instance Eq Integer where 
      x == y   = <some native code>

That is, Eq is a class we can apply to any type a, as long as we have a way of defining the (==) operator, which takes two things of type a and returns a bool. We would like to say that Integer is an instance of this typeclass Eq.

You can use classes to express rules about multiple types, by just adding more type variables to the class definition. The Haskell wiki gives the example of matrix and vector multiplication, with "class Mult a b c", "instance Mult Matrix Matrix Matrix", and "instance Mult Matrix Vector Vector".

(One of the problems that comes up when doing this is that type inference doesn't know how to resolve overloaded types. FunctionalDependencies lets you add the "| a b -> c" syntax, which means "the type c in this typeclass is uniquely determined by whatever the type of list is, nobody can instantiate this typeclass twice for the same type of a and b". But don't let that syntax confuse you into thinking that a function, in the normal sense of something taking inputs and producing outputs, is being defined; it's just defining relationships between objects. almost Prolog-style.)

What he's doing is defining type classes for what us normal people would think of as functions. Nil and Cons are separate, unrelated types: in C++ terms, Nil would be class Nil {}, and Cons would be template <typename x, typename xs> class Cons {}. Keep in mind that x and xs are type arguments, not actual data members!

Then there are typeclasses with no functions; nothing needs to be implemented to be a member of the typeclass, but the type constraints need to be satisfied.

So we say that the two types a=Nil and b=Nil satisfy the "First" typeclass, and that the two types a=Cons x more and x also satisfy the "First" typeclass, for any type x (and any type more).

Then ListConcat gets to type constraints: the three types (Cons a as), bs, and (Cons a cs), taken together, satisfy the typeclass ListConcat as long as the three types as, bs, and cs also satisfy it. So now we're asking the type inference algorithm to start doing some recursion and probably some backtracking, but it's all hidden.

So on and so forth, with Peano integers and everything else, until we get to the meat of the queens problem: an instance of the 6-queens problem can be constructed if there are six queens not attacking each other.

Then he asks the typesystem to run type inference and figure out a plausible type for the 6-queens problem.

What's the runtime? Who knows.

What's the runtime?

Zero by the usual definition, but then again it's cheating.

> Zero by the usual definition

Well, one.

He never actually runs the program, he just asks for its type. So zero is defensible.

Fair enough.

Thank you! Your explanation made the most sense, a lot of the other ones went over my head. This is so clever and fascinating.

Still the most educated form of trolling to be seen around here. Beautiful and always worth a few good snickers.

Template without the name

This is his third one on interviewing and definitely the funniest. I wonder if he actually has been interviewing and doing this?

There was a great talk at Haskell Exchange 2016 along similar lines - defining a lot of complex functionality at the type level to derive correct functionality. https://skillsmatter.com/skillscasts/8893-is-a-type-a-lifebu...

This was a funny article :)

Sad to say, this is exactly the sort of magic that, as the conclusion suggests, gets people not hired. Even on this very enlightened forum people argue in favour of less knowledgeable candidates (even with all else being equal).

Such a lack of imagination. Hire a good enough warlock, and requirements can be fulfilled at compile time - you just need well-typed customers, which is the tricky part.

I think you'd need the right kind of position for someone like this. Presumably, Criss wasn't trying to hire for a council of Haskell type-warlocks. Toss this person into a typical dev role, and you've got a recipe for boredom on their side and confusion on the part of the rest of the team.

But the solutions shown in this series are just pointlessly esoteric. I'm not actually sure what the point of this series is.

It's to get aphyr more twitter followers.

The whole point _is_ that it's pointless esoterica.

Like music/art/religion/gourmet-cooking/morris-dancing/synchronized-swimming.

If it's "your thing", it's _wonderful_. It might not be your thing, and that's fine too.

If you're exclusively a bro-country fan, you probably don't appreciate jazz or classical - and that's OK, I hope you get immense joy from your bro-country music.

I took it as a commentary about how stupid tech interviews are. The scenarios all present a company rejecting someone who is clearly more skilled than the interviewer.

Yeah, well, that's based on a fallacy. You're assuming that there's a single scale and being more "skilled" on that scale means you should get hired.

But that's not necessarily what interviewing is all about. Type-level programming is cool but wildly inappropriate for most jobs - that's part of the humor.

You are not your job, or your resume, or your ability to pass an interview. There are all sorts of ways people can be elite that are mostly orthogonal to a particular job.

Functional programming elitism is an interesting convergence between old-school SICP-reading academic greybeards, and modern day Haskell hipsters who like purity in their languages. Both would like to hate on imperative-coding industry squares like the technical interviewers in all of these stories.

Does it need a point? It's well written entertainment, with some neat programming trickery.

It's like "let's rewrite X in JavaScript" but on a couple of magnitudes higher level.

That's OK, you're not the target audience.

It's odd. There are people who complain on Hacker News about interviewers who ask about algorithmic complexity: "when are we ever going to need this?"

This is about wasting an interview demonstrating a semi-obscure technique that's fascinating but mostly useless, and it gets widely praised.

Seems like it's just that fantasizing about turning the tables on an interviewer is fun, never mind whether it makes sense or not.

Type level programming is a powerful feature. This is of course a humorous show off which still neatly demonstrates it.

Do you have no sense of humor?

On the contrary, I found his post a well crafted sendup of the typical HN commentariat who didn't get it.

Are you a technical interviewer?

I think it's clear that the article is satire.

It obviously draws on some commonly identifiable tech interview tropes, and that's what gives it its comedic value, but I don't it intends to say that the way the witch deals with those interviews is the model way.

Reply on news.ycombinator.com