Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Если вы хотите устроиться на работу колдуном-программистом, вам придется пройти собеседование с написанием кода на бумажке. Все инженеры периодически их проходят - иногда в качестве утреннего ритуала, вместе с аккуратным расставлением окошек терминала по астральному плану, компульсивным выполнением команды ls во всех папках (на всякий случай, если за ночь что-либо поменялось). С теми же чувствами другие копаются в дальнем ящике на кухне, где лежат всякие отвертки, бесхозные патрубки, и прочие пластмассовые изделия - белые вороны среди бытовых принадлежностей, чье первоначальное предназначение давно забыто (а может и никогда не было известно), но о которых мы все равно вынуждены заботиться.
Сегодня мы обсудим один из типичных вопросов на таком интервью - развернуть связанный список.
Первым делом вам нужен список. Вы очищаете рабочее пространство от ненужных окон терминала, насыпаете соль в виде двух защитных скобочек и уходите в рекурсию, призывая список из бездны:
(defn cons [h t] $(if % h t))"Это не список", говорит собеседующий. "Это условное утверждение".
"А что есть списки", со вспыхивающими глазами отвечаете вы, "как не альтернативы?".
user=> (def x (cons 1 (cons 2 nil)))
#'user/x
user=> (x true)
1
user=> ((x false) true)
2"Что такое x?" Собеседующий изо всех сил старается выглядеть дружелюбным. Покажите ему ответ в REPL, но не забывайте ни на секунду: он вам не друг. При входе в офис вы дали клятву, которая это запрещает.
user=> x
#object[user$cons$cell__4431 0x3b89cc1c "user$cons$cell__4431@3b89cc1c"]"Чтобы познать сущность, ей нужно дать имя", произносите вы. Истинные имена обладают силой. Язык K, который придумала Урсула К. Ле Гуин, является одним из старейших и наиболее емких форм магии. Наделить язык буквой собственного имени - это оставить в нем частичку своей души. Ваши собственные инициалы всплывают в памяти.
"Эммм, ну хорошо, а как получить элемент этого списка?"
Прекрасный образ в вашем воображении разворачивается, как красная ковровая дорожка под вашими босыми ногами. Вчера по телевизору показывали вручение премии "Оскар", но вы жаждете поцелуев других звезд на своей коже - как в ту ночь, на норвежском острове Сёрёйя, когда вы называли луну своей любовницей. Если не считать проверки границ, то получается с первого раза:
(defn nth [l n]
(when l (if (= 0 n)
(l true)
(recur (l false) (dec n)))))"А можете показать, ну, обычный список? Как в Python?"
Вы стискиваете зубы, упираетесь ногами в пол и вытягиваете из бездны автоформаттер. На ваших руках мозоли, а веки усыпаны черными, как сажа, кристаллами-снежинками. Любое действие дается дорогой ценой - кроме, разумеется, чистых функций, у которых нет побочных эффектов.
(defn prn-list [l]
(print "(")
(loop [l l]
(if (nil? l)
(print ")\n")
(do (print (l true))
(when (l false)
(print " "))
(recur (l false))))))Нет времени на осмысленные имена переменных, примеры и комментарии. Это же интервью, здесь время на вес золота. Вы вспоминаете свою бабушку, которая программировала на Haskell, и все, что вам от нее передалось. Вы - ее продолжение!
user=> (prn-list (cons 1 (cons 2 (cons 3 nil))))
(1 2 3)Собеседующий обнадеженно улыбается. Теперь вы на знакомой ему земле (или, скорее, парите над ней). "А теперь, чтобы его развернуть..."
Вы хватаете его за ладони. Шестеренки в его голове бешено вертятся, сердце колотится и рвется из груди при виде того, как из-под вашего курсора змеится заклинание на древнем языке:
(defn reverse [l]
(loop [r nil, l l]
(if l
(recur (cons (l true) r) (l false))
r)))
user=> (prn-list (reverse (cons 1 (cons 2 (cons 3 nil)))))
(3 2 1)Вырвавшись, он мямлит что-то вежливое и застегивает толстовку, чтобы не замерзнуть. Будут и другие собеседования, но вам не нужно на них присутствовать. Отправьте вместо себя орла.
Они, разумеется, откажут вам, стыдливо объясняя это культурными различиями. Вылетайте через окно. Этот офис все равно не смог бы вместить вас.
