「Habrahabr」の読者に、 Kyle Kingsbury（別名「Aphyr」）の記事の翻訳を提供します。
以前： 技術面接の実施
教会の台頭のずっと前の早い時期に、すべての呪文は純粋な機会に発音され、すべての行動は許可され、死は当たり前でした。 多くの魔女は魔法のせいで不自由になりました;彼らはねじれた、艶をかけられた木々と燃えている石の円の中心で壊れていて、水の下でも消えませんでした。 いくつかは完全に姿を消したか、mountainに沿って移動し始め、足で地面に触れず、息で空気を温めませんでした。
子供の頃、あなたはジャッジメント・ファイアから3回生まれ変わり、世界を旅してサイドルを演じたグルウェイグ・テン・ハイエルの話を聞きました -未来の読書と神経叢。 彼女の予測（そして多くがあった）は有名になりました-それらは世界中を歩いている人々によってさえ繰り返されました-しかし、彼女の生存は物語を変えました。 サイドルのとしたトランスの中で、彼女は自分の未来を予見し、死を征服しました。 彼女の呪文は決して破れず、彼女は亡命女性、あなたの祖先の友人になりました。 オーディン自身が彼女から不滅を学んだと言われています。
今日に至るまで、すべての魔女はハイアールに恩恵を受けています。 最近では、古代の構造化されていない魔法に飛び込む人はほんのわずかです。 呪文が書かれている言語自体は、構造内でseidr自体によって安定化され、誘発されたエネルギーを安全な方法で、多かれ少なかれ通過させます。 もちろん、時折爆発が発生します。 しかし、それらは主にさまざまな燃える眉毛からのものであり、興味深い形の新しいフィヨルドを作成していません。
「すべて大丈夫ですか？」
インタビュイー-クリス、バッジの名前から判断すると-谷の習慣に対応する非常に若いです。 彼はスウェットシャツを着ています。ブランドの不足から判断すると、少なくとも100ドルはかかります。 動物とはまったく似ていないので、あなたは考えます。 通常、このようなことはあなたにとって簡単です。
「どういうことですか？私はそうは思わない。」あなたは会議室を見回し、確認を求めているかのように見ます。 壁は対立回避とSlackメッセージの匂いがします。
「まあ、ええと、結構です。はい、おそらくあなたは正しいでしょう。」 彼の声はti病に聞こえます。 「それにもかかわらず、ちょっとしたエクササイズをしたいと思います。問題を解決する方法を理解できるように、簡単なプログラミングタスクです。」
黒曜石のかけらからナイフで問題を解決したら。 クリスはあなたがしたことを繰り返す力があるのだろうか。
「だから...このパズルはNクイーンと呼ばれ、非常にシンプルです。NxNサイズのチェス盤では、このボードにNクイーンを安全に配置する方法を見つける必要があります。」
白い壁に通常の8 x 8チェスフィールドを描き、中央に8人の女王のグループを慎重に配置します。 彼らは平等にお互いに話すためにタイトなサークルに立っています。
「ええ、いや-それは間違っています。参照してください。この女王は、これらの4つを一度に削減できます。」
「あなたは本当にできません」、あなたは石のように冷たい声で尋ねます、「同じ部屋でお互いを殺そうとしない8人の強力な女性を想像するために？」
「ええと...それは単に問題の声明です。」
おそらく、これらは戦っている氏族の家長です。 彼らは停戦について話し合うために集まったが、彼女が短剣に到達できるなら、一方は他方を信頼しない。 これはあなたの種類の歴史でも起こりました。
「任意の言語を使用できますか？」
「もちろん。」
彼が自分の間違いを理解するまで素早く行動してください。
{-# OPTIONS_GHC -fno-warn-missing-methods #-} {-# LANGUAGE MultiParamTypeClasses #-} {-# LANGUAGE FunctionalDependencies #-} {-# LANGUAGE FlexibleInstances #-} {-# LANGUAGE UndecidableInstances #-}
「ああ、これはHaskellです！大学で彼に教えました！」 彼は立ち去り、鼻を鳴らす。 「決定できないインスタンス？」
「Haskはカテゴリではないので、使用する必要があります」と喜んで彼に知らせます。
「ああ、そうだ」クリスは決定的な意見を述べ、特に誰にも言及しません。 「したがって、私たちは通常、Haskellのサブセットで考えましたが、そこでは型に低い値はありませんでした。」
「あなたはそれをすることができます」とあなたは同意しますが、クリスがあなたを聞くにはあまりにも静かで、その間は反対に完全に自信があります。
nil = undefined
今、不快な質問があります。 それを拒否し、頭に浮かんだ最初のものを発行する必要があります。 「女王の地位を維持するには、リンクリストが必要ですよね？」
「もちろん、またはベクトル。」
「リストの方が簡単です。」
「さて、あなたにとってより便利なものを使用してください。」
voidからリンクリストを呼び出します。 彼はスクリーンの表面に浮かんでいます。古典的な構造で、千通りに表現されていますが、常に美しいです。 あなたは満足してため息をつきます。
data Nil data Cons x xs
「組み込みリストを使用できますか？」 -クリスに尋ねます。クリスの眉は忍び寄っています。
「なに？」 「彼が何について話しているのかわかりません。」 「いや、いや-ここでライブラリ全体をドラッグする必要があります。内部でそれらを特定する方が簡単です。」
class First list x | list -> x instance First Nil Nil instance First (Cons x more) x
「キーワード「クラス」は関数のシグネチャを定義します」-何かを忘れたように見えるクリスを思い出させます。 「最初にリストを取得し、そこから値xを返します。関数には2つのインスタンスがあります。Haskellはパターンマッチングを使用して呼び出すものを選択します。リストの最初のNilはNilを返し、セルの最初のConsはセルxの値を返します」
言われたものを同化させ、リストの接着に進みます。
class ListConcat abc | ab -> c instance ListConcat Nil xx instance (ListConcat as bs cs) => ListConcat (Cons a as) bs (Cons a cs)
「そして、どんな矢印？」 クリスは尋ねます。 あなたはそれが意味を意味すると彼に言った 「矢印の後にListConcatを取得するには、矢印の前にListConcatが必要です。」
理解を理解します。 「A.そうです！これは再帰です。ListConcatが両側に表示されるためです。そして、Nilの定義が基本ケースです。」
「まさに」 あなたはクリスをとても誇りに思っています。 彼はまさに足を踏み入れる。 「そして、これはリストのリストを接着したい一般的なケースです。」
-- 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
あなたが好むよりももっと集中する必要があったので、私たちはもっとシンプルなものに後退しました。 「ブール値を扱いましょう」と、通常夕食に招待する口調で提案します。
「なんで？」
「もちろん必要だからです。」
無効から2つの無意味な定数を取得し、それらを意味で埋めます。
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
フレイアはおそらく喜んでいるでしょう。 世界への代数の誕生は素晴らしい出来事です。
「そして、私たちは女王の座標を保存するために整数も必要だと思います」とつぶやきます。 「私たちはポジティブな座標でのみ仕事をしているので、通常のペアノのデザインで十分です。」 あなたは髪型から髪を引き出し、それに結び目をします。
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
「あなたは...自然数を手動で決定しますか？なぜですか？」
「Haskellは数学者向けです」と説明します、「私たちは常に用語を定義します。」
-- 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)
「待って、待って」クリスは割り込む。 「そうではありません...ここで型宣言は必要ないのですか？少なくとも、関数の場合は？」
あなたは優しく微笑む。 「Haskellは、動的に型付けされたインタープリター言語です。」
クリスはカエルを飲み込んだようです。
「見てください。1対1かどうかを確認しましょう。」
class LegalCompare t | -> t where legalCompare :: t instance (PeanoEqual (SZ) (SZ) t) => LegalCompare t *Main> :type legalCompare legalCompare :: True
「見てください。LegalCompareはTrueです。次に、誤った比較を行う式を作成してみましょう。たとえば、TrueとListを比較してみましょう。」
class IllegalCompare t | -> t where illegalCompare :: t instance (PeanoEqual True (Cons Z False) t) => IllegalCompare t
「参照してください。完全にロードされます。式を実行しようとすると壊れるだけです。Haskellは怠け者であることに注意してください。」
*Main> :type illegalCompare illegalCompare :: PeanoEqual True (Cons Z False) t => t
「ここにいる！実行時にエラーを入力してください。」
「しかし、エラーについては何も書かれていません...」
「そうですね、Haskellのエラーメッセージは理解が難しいことで広く知られています。」
クリスはかなり病気に見えます。 高次関数に切り替える機会を利用してください。
「残念なことに、Haskellにはカリー化がありません。そのため、関数を部分的に使用する独自のツールを作成する必要があります。関数の一般化された単項使用のシグネチャは次のとおりです。」
class Apply far | fa -> r
「入力aを受け取ってrを返す関数fだけ」、変数名の曲はほとんど歌のように聞こえます。 「部分的に使用する場合、Partial1、Partial2などのデータ型を定義できますが、必要なのはそれらの一部のみであるため、必要な関数の厳密にカリー化されたバージョンを定義する方が簡単です。
data Conj1 list instance Apply (Conj1 list) x (Cons x list)
深呼吸をして、あなたの精神をこれらのコンクリートの形から高次関数の放射高さまで急上昇させてください。
-- 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
しばらくの間、具体的な意味の世界に戻らなければなりません。 少なくとも物理的には、クリスはまだここにいます。 極端な寒さのおかげで、ノートパソコンの画面は紫色の色調の豪華な混乱に変わりましたが、コードの深さはまだ認識できます。 画面は、夕暮れ時の凍った湖を思い出させます。 液晶。
「クリス。クリス。」 彼はあたかも暗闇の中から光の中へと飛び込むように素早く瞬きます。 美しい目。 あなた自身の目がまだ色を持っていた時代を覚えていますか。 「準備ができました。」
「はい、いいです。」
「クイーンはボード上の2つの座標xとyによって決定されます。また、部分的に使用されるコンストラクタを作成して、クイーンを指定されたx座標に配置します。」
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
「はい、クイーンズ！」 -あなたはつぶやきます。 残念ながら、これはインタビューのようなものではありません 。
各クイーンは、8方向に攻撃できます。 あなたはいつもそれが隠phorだと思っていました。
-- 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
部屋に新しい女王が現れ、位置を狙います。 彼女は同僚に注意を払い、手の届かないところに滞在します。 彼女はどこで起きる必要がありますか？ 宇宙のパックを想像してください-代替世界、それぞれが異なる位置に女王が含まれています。
-- 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'
「そして今、私たちは再帰を開始します」あなたはささやき、制御スレッドによって固定された呪文を自分自身に回します。 各構成ごとに、各有効な位置で、行ごとに1つのクイーン。 スタートアップのウェブサイトの「私たちについて」のページがどのように見えるか想像してみてください。
-- 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
クリスは、ひどい損失を被った人や、おそらく近くの爆発を目撃した人のように、あらゆるものを習慣的に調べます。 そっと肩に乗せてください。 「ごめんなさい！」とあなたはささやきます、「すべては準備ができています、決定は近いです。」
*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)))))
見てみましょう、美しい結論はまさにそのような問題を設定し、垂直軸に沿って魅力的なゼロの線を作成します。 「つまり、5.1、4.3、3、5、2.0、1.2、および0.4のクイーンがいます。クリスですか？」
クリスは非常に長い間あなたを見つめます。 「あなたは…本当の意味を書いたことは一度もありません。あなたは...タイプシステムが値を含まなければならないことを理解していますよね？」
「いいえ」あなたは副キャプテン証拠として彼に知らせます。 「いいえ、そうではありません。」
彼はこれまで椅子に身を乗り出し、転がろうとしていると思うので、両手で顔をこすります。 あなたは、すでにseidrを介して拒否メールを見て、彼が言うことを知っています。
「ご連絡いたします。」
Patrick ThompsonとConrad Parker Type Level Insanityに心から感謝します。