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?
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 :)
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.
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.
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
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?
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.
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.
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.
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.
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...
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.
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.
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.
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.
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.
https://aphyr.com/posts/340-reversing-the-technical-intervie...
https://aphyr.com/posts/341-hexing-the-technical-interview