Как написать FizzBuzz на собеседовании

Здравствуй, Хабр.

Недавно я проходил собеседование в одну солидную айтишную контору. Когда мы разобрались с формальностями, начался технический этап, на котором мне поручили написать fizzbuzz. По не вполне понятным мне причинам обсуждение решения этой задачи растянулось на довольно большой срок, после которого время на интервью уже вышло. Мы расстались на хорошей ноте, и мне пообещали перезвонить. Пока я жду оффер, я решил поделиться своим опытом прохождения интервью с широкой публикой, равно как и своим решением, ибо они показались мне заслуживающим внимания.

Начинаем

Интервьюер был настроен доброжелательно.

— Напишите программу, которая бы вывела числа от одного до ста включительно по следующим правилам: если число делится на 3, то выведите "fizz", если число делится на 5, то выведите "buzz", если число делится и на 3, и на 5, то выведите "fizzbuzz", а если ни одно из этих условий не выполняется, то выведите число как обычно.

— Хорошо. Как отделять числа друг от друга? По одному на строчку?

— Как вам удобно.

— Ясно. Какой язык программирования я могу использовать?

— Любой, с которым вам удобно. Впрочем, крайне желательно, чтобы это не был какой-то эзотерический язык программирования. А то у нас как-то один кандидат — доброжелательный интервьюер на секунду поёжился — как-то развернул список на чём-то вроде Haskell и даже тестов не написал.

— Спасибо, я буду использовать Rust.

— Это тот новый хайповый язык программирования?

— Да. Он похож по синтаксису на C, так что проблем с пониманием возникнуть не должно.

В этот момент интервьюер облегчённо выдохнул.

— Хорошо. Можете начинать.

Я открыл Rust playground и начал писать код:

struct Z;
struct S<T>(T);

Интервьюер слегка нахмурился.

— Не могли бы вы пояснить, что вы делаете?

— Конечно. Я делаю свои собственные числа согласно аксиоматике Пеано. Как видите, эти два определения напрямую отражают аксиомы: натуральное число — это либо ноль, либо некоторое иное натуральное число, увеличенное на единицу.

— А зачем вам эти определения? Разве вы не можете обойтись встроенными числовыми типами?

— Разумеется, могу. Однако в той задаче, которой вы мне дали, отсутствуют входные данные, весь вывод программы можно подсчитать заранее, поэтому я бы хотел избежать ненужных вычислений в рантайме. С другой стороны, все преобразования над типами гарантированно выполняются на этапе компиляции — всё-таки Rust статически типизированный язык — поэтому вынесение чисел на уровень типов позволит делать меньше в рантайме.

— А, ну если вы так считаете, — сказал интервьюер после некоторой паузы — хорошо, продолжайте.

Я где-то читал, что на собеседовании хорошим тоном является проговаривать свои мысли вслух. Поэтому, а также из-за вопросов интервьюера я решил самостоятельно комментировать то, что пишу:

— Конечно, мы можем составить из этих S нужную нам сотню, но это несколько утомительно и вдобавок увеличивает шанс внести ошибку из-за опечатки, поэтому я реализую способ складывать подобные числа:

trait Add<Rhs> {
    type Sum;
}

type SumOf<N, M> = <N as Add<M>>::Sum;

— Для того, чтобы составить сумму из чисел, записанных в типах, нам потребуются трейты (некоторые также называют их "типажами", но мне этот термин не очень нравится). Функций на уровне типов в Rust, увы, нет, но трейты с ассоциированными типами позволяют до некоторой степени их эмулировать. Сейчас я написал новый трейт, который будет сопоставлять Self (типу, для которого определяется трейт) и Rhs их сумму через ассоциированный тип Sum. Так как развёрнутый синтаксис, используемый для сопоставления типу его ассоциированного типа определённого трейта, несколько шумный, для удобства я определил псевдоним, который скрывает эту громоздкую конструкцию.

Я сделал небольшую паузу, чтобы дать интервьюеру переварить услышанное, и продолжил:

— В силу того, что определение чисел у меня индуктивное, определение суммы также должно быть индуктивным. Базой индукции, очевидно, является случай, когда одно из слагаемых равно нулю: в этом случае сумма равна другому слагаемому. Но что делать в шаге индукции, когда мы складываем два ненулевых числа? В таком случае мы можем одно слагаемое — скажем, первое — уменьшить на единицу, а другое — увеличить на единицу, и для вновь образованных слагаемых подсчитать сумму. Сумма от этого, разумеется, не изменится, но мы свели задачу к меньшей. Рано или поздно это уменьшение приведёт к тому, что одно из слагаемых станет нулевым, и мы сможем воспользоваться базой индукции. Выразим это в коде:

impl<N> Add<N> for Z {
    type Sum = N;
}

impl<N, M> Add<M> for S<N>
where
    N: Add<S<M>>,
{
    type Sum = SumOf<N, S<M>>;
}

— Имея на руках сложение, уже несложно выписать нужные нам константы: три, пять и количество требуемых элементов: сто.

type One = S<Z>;
type Two = SumOf<One, One>;
type Three = SumOf<One, Two>;
type Five = SumOf<Two, Three>;
type Ten = SumOf<Five, Five>;
type TwentyFive = SumOf<Five, SumOf<Ten, Ten>>;
type Fifty = SumOf<TwentyFive, TwentyFive>;
type OneHundred = SumOf<Fifty, Fifty>;

type N = OneHundred;

Составляем список

— Окей, с числами мы разобрались. Теперь нам нужно каким-то образом отсчитать от единицы до сотни. Судя по всему, нам понадобится список из них. Списки также несложно определить индуктивно: это или пустой список, или пара из первого элемента списка и всех остальных элементов списка:

struct Nil;
struct Cons<H, T>(H, T);

— Кстати, как нетрудно видеть, определённые мною числа изоморфны спискам из элементов unit-типов, то есть я вполне мог бы вместо S<N> использовать Cons<(), N>. Но я решил этого не делать, чтобы сохранить ясность кода.

Интервьюер медленно кивнул. Убедившись, что меня понимают, я продолжил:

— Теперь встаёт вопрос, а как нам составить список из чисел от единицы до сотни включительно. К сожалению, попытка сделать это напрямую вынудит нас задать на числах отношение порядка, и в силу того, что требования к типам в Rust вычисляются не лениво, подход в лоб приведёт нас к рекурсии при вычислении ограничений на типы. Поэтому поступим по-другому: сделаем сначала список от сотни до единицы, а потом обратим его.

Нам опять потребуется функция на уровне типов, которую мы выразим как трейт с ассоциированным типом:

trait RangeDownFrom {
    type Output;
}

impl RangeDownFrom for Z {
    type Output = Cons<Z, Nil>;
}

impl<N> RangeDownFrom for S<N>
where
    N: RangeDownFrom,
{
    type Output = Cons<S<N>, N::Output>;
}

type MakeRangeDownFrom<N> = <N as RangeDownFrom>::Output;

— Кстати, кое-что с этой функцией не так. Вам очевидно, что именно?

Интервьюер немного помолчал, а потом ответил:

— Наверное… Но не могли вы сами сказать?

Сообразив, что меня проверяют, я продолжил со своим ответом:

— Эта функция делает список, который кончается нулём, а не единицей. К счастью, отбросить потом голову списку — плёвое дело, а в некоторых аспектах это даже окажется удобным, — тут я виновато улыбнулся — я уже прикидывал, как такое делать.

Интервьюер тоже улыбнулся, но, как мне показалось, несколько натянуто. Я перешёл к следующей части решения:

— Обращение списка, как известно, является банальной левой свёрткой по списку с операций cons с аргументами в обратном порядке и пустым списком в качестве начального значения. К сожалению, система типов Rust недостаточно продвинута, чтобы выразить на уровне типов функции высшего порядка, поэтому свёртку придётся писать руками. Впрочем, она тут достаточно простая: для пустого списка нам достаточно вернуть аккумулятор, а для cons нам надо отделить голову, приставить её к аккумулятору и продолжить обращение с хвостом списка. Всё это достаточно коротко и ясно выражается в коде:

trait ReverseWith<Acc> {
    type Output;
}

impl<Acc> ReverseWith<Acc> for Nil {
    type Output = Acc;
}

impl<Head, Tail, Acc> ReverseWith<Acc> for Cons<Head, Tail>
where
    Tail: ReverseWith<Cons<Head, Acc>>,
{
    type Output = <Tail as ReverseWith<Cons<Head, Acc>>>::Output;
}

type Reverse<List> = <List as ReverseWith<Nil>>::Output;
type RangeTo<N> = Reverse<RangeDownFrom<N>>;

Считаем тройки и пятёрки

— Теперь перейдём к сути задания. От нас требуется классифицировать числа по их остаткам от деления на три и на пять. В принципе, мы можем реализовать деление с остатком чисел Пеано, но это заняло бы довольно много нудного кода. Вместо это попробуем прикинуть, как добиться нужного результата меньшими усилиями.

Я на время откинулся от клавиатуры.

— Что вообще означает, что остаток числа от деления на, скажем, три, равен нулю? По другому это можно сформулировать так, что если мы начнём считать от нуля, то каждое третье число будет, очевидно, делиться на три без остатка. Мы можем пройтись по всему списку, вручную отмечая каждый третий элемент. Конечно, мы не хотим повторять себя и хотим использовать схожий подход для пятёрки. Мы хотим абстрагироваться от конкретного числа, используя счётчик, который будет инкрементироваться для каждого элемента списка по некоторому модулю. Таким образом, нам нужно определить операцию инкрементирования по модулю некоего числа n, а потом прикрепить к этому счётчик и поднять эту операцию на уровень списков.

— Или же нет? — прервал я сам себя — при таком подходе мы неизбежно столкнёмся с теми же проблемами, что и при наивной реализации RangeTo: бесконечной рекурсии требований к типам. С другой стороны, реализовать декремент по некоторому модулю мы спокойно можем. При этом позиции, где счётчик принимает значение ноль, останутся теми же самыми — а именно они нам и нужны.

Снова определим результат индуктивно: ноль, уменьшенный на единицу по некоторому модулю, равен числу, на единицу меньшему модулю, а число, большее единицы, декрементированное по тому же модулю, ну, то же самое число, только без единицы. В коде это выглядит менее неловко, чем мои слова, — я снова принялся печатать:

trait DecrementByMod<M> {
    type Output;
}

impl<T> DecrementByMod<S<T>> for Z {
    type Output = T;
}

impl<M, T> DecrementByMod<M> for S<T> {
    type Output = T;
}

type DecMod<T, M> = <T as DecrementByMod<M>>::Output;

Теперь нам нужно прикрепить счётчик к списку. Конечно, можно сказать, что это какая-то правая свёртка, но тут это ясности не прибавляет, проще написать код:

trait EnumerateFromWithCycle<Start, N> {
    type Output;
}
type EnumeratedFromWithCycle<T, Start, N> =
    <T as EnumerateFromWithCycle<Start, N>>::Output;

impl<Start, N> EnumerateFromWithCycle<Start, N> for Nil {
    type Output = Nil;
}

impl<Start, N, Head, Tail> EnumerateFromWithCycle<Start, N> for Cons<Head, Tail> 
where
    Start: DecrementByMod<N>,
    Tail: EnumerateFromWithCycle<DecMod<Start, N>, N>,
{
    type Output = Cons<
        (Head, Start),
        EnumeratedFromWithCycle<Tail, DecMod<Start, N>, N>,
    >;
}

Код становится немного угрожающим, но более сложных наворотов на уровне типов нам уже не потребуется. Введём алиасы для нужных нам операций:

type EnumerateFromZeroWithCycle3<T> = EnumerateFromZeroWithCycle<T, Three>;
type EnumerateFromZeroWithCycle5<T> = EnumerateFromZeroWithCycle<T, Five>;
type FizzBuzzEnumerate<T> = EnumerateFromZeroWithCycle5<
    EnumerateFromZeroWithCycle3<T>>;

Осталось только отобразить значение со счётчиками на нужное значение на уровне типов, что фактически сводится к сопоставлению с образцом:

struct Fizz;
struct Buzz;
struct FizzBuzz;

trait ToFizzBuzz {
    type Output;
}

type FizzBuzzed<T> = <T as ToFizzBuzz>::Output;

impl<T> ToFizzBuzz for ((T, Z), Z) {
    type Output = FizzBuzz;
}

impl<T, N> ToFizzBuzz for ((T, Z), S<N>) {
    type Output = Fizz;
}

impl<T, N> ToFizzBuzz for ((T, S<N>), Z) {
    type Output = Buzz;
}

impl<T, N, M> ToFizzBuzz for ((T, S<N>), S<M>) {
    type Output = T;
}

impl ToFizzBuzz for Nil {
    type Output = Nil;
}

impl<Head, Tail> ToFizzBuzz for Cons<Head, Tail> 
where
    Head: ToFizzBuzz,
    Tail: ToFizzBuzz,
{
    type Output = Cons<
        Head::Output,
        Tail::Output,
    >;
}

Если честно, моего внутреннего пуриста немного коробит, что одно и то же определение используется и для отдельных элементов, и для списка целиком, но вреда тут это не несёт, а введение отдельного трейта для операций на списках не дало бы никаких преимуществ.

Я сделал небольшую паузу, чтобы выдохнуть, и продолжил:

— Что ж, у нас почти всё готово, осталось лишь собрать всё это воедино — и учесть тот факт, что список в итоге начинается с нуля и потому нуждается в срезании головы:

trait TailOf {
    type Output;
}

type Tail<T> = <T as TailOf>::Output;

impl<Head, Tail> TailOf for Cons<Head, Tail> {
    type Output = Tail;
}

type FizzBuzzList<T> = FizzBuzzed<Tail<FizzBuzzEnumerate<RangeTo<T>>>>;
type List = FizzBuzzList<N>;

Фактически, нам сейчас даже не нужно писать никакого рантайм-кода: мы можем просто написать что-то с использованием List, что не будет тайпчекаться, и компилятор выведет нам тип сам, — я с энтузиазмом набросал код:

fn foo() {
    let _: List = ();
}

Затем я нажал Ctrl+Enter и через пару секунд с довольным видом показал интервьюеру ошибку компиляции:

error[E0308]: mismatched types
   --> src/lib.rs:162:19
    |
162 |     let _: List = ();
    |            ----   ^^ expected struct `Cons`, found `()`
    |            |
    |            expected due to this
    |
    = note: expected struct `Cons<S<Z>, Cons<S<S<Z>>, Cons<Fizz, Cons<S<S<S<S<Z>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<Z>>>>>>>, Cons<S<S<S<S<S<S<S<S<Z>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
            found unit type `()`

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous error

Переводим в строки

Интервьюер посмотрел на экран, прокрутил его вплоть до конца длинной ошибки, немного помолчал со сосредоточенным видом, а потом спросил меня:

— Извините, а что в итоге сделала ваша программа?

— Моя? — я развёл руками — моя программа не сделала ничего. В конце-концов, она не скомпилировалась.

Интервьюер вздохнул.

— Это не то, что от вас требовалось. От вас требовалось написать программу, которая будет, гм, запускаться, и выдавать нужный результат. Вдобавок, этот вывод, возможно, и правильный, но я не могу его прочитать, так что я не смогу сказать, правильный он или нет.

Я хлопнул себя по лбу.

— Ну конечно! Я совсем забыл про начальную задачу. Что ж, технически нам достаточно наваять скрипт на баше, который будет вызывать rustc на этом файле, но я согласен, что вывод не особо читаемый. Выходит, нам требуется сопоставить каждому элементу списка строковое значение. Для структур Fizz, Buzz и FizzBuzz это делается тривиально через трейт с ассоциированной константой строкового типа, а вот для чисел Пеано это несколько сложнее. Создание на этапе компиляции строки из числа в Rust является почти невыполнимой задачей, так что мы поступим иначе: будем использовать пару из массива байт и длины итоговой строки. Благодаря системе типов Rust мы легко можем объединить обе возможности в одном типе:

enum Str<const N: usize> {
    Plain(&'static str),
    Decomposed([u8; N], usize),
}

Как вы могли заметить, этот тип параметризован максимальным размером байтового представления строки. В каком-то смысле это перебор, поскольку мы могли бы указать, скажем, массив из трёх байт, которых бы хватило для представления всех чисел до сотни включительно, но мне не хотелось бы затачиваться на конкретную верхнюю границу, тем более что требуемую длину мы всегда можем подсчитать. Что ж, займёмся переводом в строку и начнём с жужжащих типов:

trait AsStr<const N: usize> {
    const VALUE: Str<{ N }>;
}

impl<const N: usize> AsStr<{ N }> for Fizz {
    const VALUE: Str<{ N }> = Str::Plain("fizz");
}

impl<const N: usize> AsStr<{ N }> for Buzz {
    const VALUE: Str<{ N }> = Str::Plain("buzz");
}

impl<const N: usize> AsStr<{ N }> for FizzBuzz {
    const VALUE: Str<{ N }> = Str::Plain("fizzbuzz");
}

Перейдём к численным типам. Вот тут уже посложнее: для перевода числа в строку нам нужно его численное значение. Значение это, впрочем, получается элементарно:

trait NumericValue {
    const VALUE: usize;
}

impl NumericValue for Z {
    const VALUE: usize = 0;
}

impl<N> NumericValue for S<N>
where
    N: NumericValue,
{
    const VALUE: usize = N::VALUE + 1;
}

После того, как мы получили на руки численное значение, вывести его строковое представление уже не так сложно: достаточно последовательно брать остатки от деления на 10 и прибавлять их к ASCII-символу нуля — тут мы эксплуатируем тот факт, что в кодировке ASCII коды для цифр идут по порядку. Главное тут — не забыть, что мы таким образом получаем цифры в обратном порядке, поэтому после окончания процесса надо обернуть порядок символов:

const fn to_str<const N: usize>(mut value: usize) -> Str<{ N }> {
    let mut s = [0; N];
    if value == 0 {
        s[0] = b'0';
        return Str::Decomposed(s, 1)
    }

    let mut i = 0;
    while value > 0 {
        s[i] = (value % 10) as u8 + b'0';
        value /= 10;
        i += 1;
    }

    let n_digits = i;
    let mut i = 0;
    while i < n_digits / 2 {
        let digit = s[n_digits - i - 1];
        s[n_digits - i - 1] = s[i];
        s[i] = digit;
        i += 1;
    }

    Str::Decomposed(s, n_digits)
}

Отлично. Теперь, получив нужное разложение, мы можем написать реализации AsStr одним махом для всех чисел на уровне типов:

impl<T, const N: usize> AsStr<{ N }> for T
where
    T: NumericValue,
{
    const VALUE: Str<{ N }> = to_str(<T as NumericValue>::VALUE);
}

И теперь уже несложно отобразить список типов на список строковых значений:

trait AsStrList<const N: usize> {
    type List;
    const LIST: Self::List;
}

impl<const N: usize> AsStrList<{ N }> for Nil {
    type List = Nil;
    const LIST: Nil = Nil;
}

impl<Head, Tail, const N: usize> AsStrList<{ N }> for Cons<Head, Tail>
where
    Head: AsStr<{ N }>,
    Tail: AsStrList<{ N }>,
{
    type List = Cons<Str, Tail::List>;
    const LIST: Self::List = Cons(
        <Head as AsStr<{ N }>>::VALUE,
        <Tail as AsStrList<{ N }>>::LIST,
    );
}

А теперь подумаем о том, как получить из Str нативную растовую строку. Для варианта Str::Plain это тривиально, мы просто достаём значение. А что делать с Str::Decomposed? Тоже ничего сложного: обрезаем массив до указанной длины и вызываем std::str::from_utf8. Тут, однако, есть парочка неприятных вещей. Первое: std::str::from_utf8 возвращает Result, с которым надо что-то делать. Второе: и конвертация из байтов в строку, и нарезка слайса делают в рантайме проверки – вообще говоря, ненужные. Мы кладём в массив только ASCII-коды, так что строка заведомо корректна для UTF-8, а возвращаемая длина никогда не превысит длину массива: если это вдруг произойдёт, функция to_str или не скомпилируется, или запаникует, в зависимости от того, была она вызвана в const-контексте или нет. Так что мы можем использовать unsafe для того, чтобы избежать этих проверок… Но поля перечисления Str — публичные, туда можно положить всё, что угодно, в том числе и данные, для которых эти предположения неверны. Чтобы обойти эту проблему, мы сделаем новый тип с приватным полем, для которого оставим два публичных конструктора: обычный для создания из литерала и unsafe для создания из массива байт и длины. Пользователь небезопасного конструктора должен обещать, что предоставляемая длина не превышает длины массива, а сами данные в массиве до указанной длины корректно закодированы в UTF-8. В таком случае мы можем спокойно вызывать небезопасные функции внутри метода, который будет конструировать строку из этого нового типа. Этот новый тип я, пожалуй, назову Str, а старый Str назову StrInner. Вынесем всё это в отдельный модуль, так как границы видимости в Rust проходят именно по ним, — я начал печатать, вынося код в отдельный модуль:

mod str {
    pub struct Str<const N: usize>(StrInner<{ N }>);
    enum StrInner<const N: usize> {
        Plain(&'static str),
        Decomposed([u8; N], usize),
    }

    impl<const N: usize> Str<{ N }> {
        pub const fn from_literal(s: &'static str) -> Self {
            Self(StrInner::Plain(s))
        }

        pub const unsafe fn from_parts_unchecked(bytes: [u8; N], len: usize) -> Self {
            Self(StrInner::Decomposed(bytes, len))
        }

        pub fn as_str(&self) -> &str {
            match &self.0 {
                &StrInner::Plain(s) => s,
                &StrInner::Decomposed(ref bytes, len) => unsafe {
                    std::str::from_utf8_unchecked(bytes.get_unchecked(..len))
                }
            }
        }
    }
}

use crate::str::Str;

Пару минут интервьюер ждал, пока я адаптировал код к новым изменениям.

— Ага, уже почти готово. Из крупного нам осталось реализовать обход списка, который у нас в итоге получится. К счастью, тут нет ничего сложного, всё опять определяется индуктивно:

trait ForEach<Arg> {
    fn for_each<F>(&self, f: F)
    where
        F: FnMut(&Arg);
}

impl<Arg> ForEach<Arg> for Nil {
    fn for_each<F>(&self, f: F)
    where
        F: FnMut(&Arg),
    {}
}

impl<Arg, Tail> ForEach<Arg> for Cons<Arg, Tail>
where
    Tail: ForEach<Arg>,
{
    fn for_each<F>(&self, f: F)
    where
        F: FnMut(&Arg),
    {
        f(&self.0);
        self.1.for_each(f);
    }
}

И ещё нам всё ещё нужно определить необходимое количество памяти для Str. Ну, тут всё элементарно:

const fn n_digits(mut n: usize) -> usize {
    if n == 0 {
        return 1
    }
    let mut ret = 0;
    while n > 0 {
        n /= 10;
        ret += 1;
    }
    ret
}

Окончательный результат

Я немного потянулся, разминая затёкшую спину.

— Итак, все необходимые части в сборе. Осталось только собрать их вместе:

fn main() {
    <List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST
        .for_each(|s| println!("{}", s.as_str()));
}

Набрав этот код, я с некоторым колебанием нажал Ctrl+Enter, и через несколько секунд отобразился результат запуска программы:

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 3.55s
     Running `target/debug/playground`
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz
fizz
22
23
fizz
buzz
26
fizz
28
29
fizzbuzz
31
32
fizz
34
buzz
fizz
37
38
fizz
buzz
41
fizz
43
44
fizzbuzz
46
47
fizz
49
buzz
fizz
52
53
fizz
buzz
56
fizz
58
59
fizzbuzz
61
62
fizz
64
buzz
fizz
67
68
fizz
buzz
71
fizz
73
74
fizzbuzz
76
77
fizz
79
buzz
fizz
82
83
fizz
buzz
86
fizz
88
89
fizzbuzz
91
92
fizz
94
buzz
fizz
97
98
fizz
buzz

Интервьюер несколько раз перевёл взгляд с экрана на меня и обратно, не проронив ни слова. Я терпеливо молчал. Через несколько секунд он спросил меня с видом, как будто только что что-то вспомнил:

— Скажите, а как вы собираетесь всё это тестировать?

Я ожидал это вопроса, так что мой ответ не заставил себя ждать:

— Что ж, в этом проекте можно выделить две части, которые можно тестировать независимо друг от друга. Одна из них — это перевод числа в декомпозированную строку. К счастью, эту часть можно элементарно покрыть тестами на основе свойств. А вот что касается построения списка, тот тут можно писать тесты этапы компиляции, которые будут проверять, что создаваемый тип равен ожидаемому. Конечно, выписывать вручную все эти типы будет несколько утомительно, но если сюда прикрутить макросы — можно процедурные для красивого синтаксиса, но, в принципе, можно обойтись и декларативными…

Интервьюер перебил меня, замахав руками:

— Хорошо, хорошо, мы вам верим.

Он вышел из кабинета, сославшись на то, что ему нужно переговорить с коллегами, а через пару минут вернулся и сказал мне, что на сегодня интервью окончено и что я могу идти домой.

— Мы вам позвоним, — сказал он мне на прощание, пожимая руку.

Правда, этого звонка я почему-то жду до сих пор.

UPD: полный код для статьи