9 ms·
Typing the technical interview
- mrkgnao 10y ago> 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 https://en.wikipedia.org/wiki/Sei%C3%B0r
- munin 10y agoThis 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 http://www.cs.brandeis.edu/~mairson/Papers/jfp02.pdf . They construct arbitrary boolean circuits from simple types and evaluate the circuits through type checking.
- binarymax 10y agoNot sure if you noticed but your username fits the mythological setting :)
- danpalmer 10y agoThere 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-lifebuoy-or-a-lamp https://skillsmatter.com/skillscasts/8893-is-a-type-a-lifebu...
- EliRivers 10y agoSad 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).
- ivanbakel 10y agoSuch 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.
- khedoros1 10y agoI 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.
- mwcampbell 10y agoBut the solutions shown in this series are just pointlessly esoteric. I'm not actually sure what the point of this series is.
- bigiain 10y agoThe 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.
- sbierwagen 10y agoIt's to get aphyr more twitter followers.
- na85 10y agoI 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.
- skybrian 10y agoYeah, 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.
- strictnein 10y ago“You’re… defining the natural numbers by hand? Why?” “Haskell is for mathematicians,” you explain. “We always define our terms.” That's just beautiful
- occultist_throw 10y agoHow.. 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?
- EliRivers 10y agoAn Italian I used to work with maintained a small shrine to Ada Lovelace on his desk.
- eckza 10y agoI always like to kindly remind people that sufficiently-advanced magic is indistinguishable from technology.
- kybernetikos 10y agoMy favourite casting of this is 'any technology distinguishable from magic is insufficiently advanced'.
- kabdib 10y ago"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]
- fasquoika 10y agoAnd then we come full circle back to heavy wizardry https://en.wikipedia.org/wiki/Magic_(programming)#Variants https://en.wikipedia.org/wiki/Magic_(programming)#Variants
- 10y ago
- strictnein 10y agoThe previous two of these were also great: https://aphyr.com/posts/340-reversing-the-technical-interview https://aphyr.com/posts/340-reversing-the-technical-intervie... https://aphyr.com/posts/341-hexing-the-technical-interview https://aphyr.com/posts/341-hexing-the-technical-interview
- hifumi 10y agoFor 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?
- lmartel 10y agoPeople like Criss who ask this question in interviews are looking for a brute force solution with recursive backtracking.
- proaralyst 10y agoIs that not what's happening here? Except GHC has the recursive backtracking built in? The code looks a lot like the equivalent Prolog implementation.
- sp332 10y agoI think you're supposed to show that you know how to do that yourself, instead of just using an existing implementation.
- Tarean 10y agoThough 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)
- andrewem 10y agoI'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 http://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf
- skybrian 10y agoIt'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.
- tener 10y agoType level programming is a powerful feature. This is of course a humorous show off which still neatly demonstrates it.
- idanoeman 10y agoDo you have no sense of humor?
- jldugger 10y agoOn the contrary, I found his post a well crafted sendup of the typical HN commentariat who didn't get it.
- Apocryphon 10y agoAre you a technical interviewer?
- kinkrtyavimoodh 10y agoI 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.
- sushisource 10y agoSo where can I buy my "Summon a linked list from the void" T-shirt?
- dimgl 10y agoAphyr is a legend. I would buy one of these shirts too.
- markwaldron 10y agoSomeone, please design this. Then post a link. I will be your first customer
- tdumitrescu 10y agoIt's like the HN generation's "I put on my robe and wizard hat"
- azeirah 10y ago> Seize two meaningless constants from the void, and imbue them with meaning. Holy shit
- deleted 10y ago[deleted]
- tempodox 10y agoThis is, literally, math.
- eli_gottlieb 10y agoYou smile kindly. “Haskell is a dynamically-typed, interpreted language.” Thou shalt not suffer a witch to live!
- tel 10y agoThis is the Old type art. It's tragic to see such unkind typing.
- carterschonwald 10y agoThis is decent prolog code ;)
- _qc3o 10y agoAny sophisticated enough type system contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of Prolog.
- marcosdumay 10y agoIt'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.
- harpocrates 10y ago> It's quite formally specified. Haha, that's a good one. Haskell, unlike SML, is _not_ formally specified. If only, if only... sobs
- carterschonwald 10y agoWay 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.
- jasondebo 10y ago"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!!!
- borp_borp 10y agoJesus christ, what the fuck is with this guy's tumblr.
- Wazzymandias 10y agoI honestly have no idea what's going on, but his writing is humorous.
- jldugger 10y agoAs 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.
- jcrites 10y agoI'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://wiki.haskell.org/Constructor#Type_constructor https://en.wikipedia.org/wiki/Kind_(type_theory) https://en.wikipedia.org/wiki/Kind_(type_theory) https://en.wikipedia.org/wiki/Peano_axioms https://en.wikipedia.org/wiki/Peano_axioms
- uyoakaoma 10y agoThis was a funny article :)
- pfarnsworth 10y agoThis is his third one on interviewing and definitely the funniest. I wonder if he actually has been interviewing and doing this?
- menssen 10y agoNope. 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.
- mrkgnao 10y agoI 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".
- deleted 10y ago[deleted]
- imh 10y agoI 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.
- GreaterFool 10y agoIt 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
- agumonkey 10y agoTemplate without the name
- tempodox 10y agoStill the most educated form of trolling to be seen around here. Beautiful and always worth a few good snickers.