#prog #ml

документация к git, идентичная натуральной: https://git-man-page-generator.lokaltog.net/

Всё ещё не готова. Кажется, я знаю, чем займусь на выходных

#meme

#prog #go

Замечательный канал, всем рекомендую.

@golang_the_best

#science #article

Замечательная статья про разбор художественного произведения с точки зрения теории информации. А в комментариях дали ссылку на замечательный рассказ Каганова на примерно ту же тему, что и Death Note

— Мне киндл постоянно какую-то дичь советует, но сегодня он превзошёл себя

#cpp #трудовыебудни

"Зря-зря" говорит техдир

#prog #meme

Девочки, переписываем программы на японский 💅

> И будем надеяться, что его не придётся ждать ещё пару месяцев

АХАХАХХАХАХХА

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

Разработчик СУБД не выкидывает мусор, а помечает его как удалённый

#prog #rust #моё

Хроники замыканий

Есть ещё кое-что, что можно сказать про замыкания.

Пожалуй, первое, с чего надо начать — так это с того, что, несмотря на то, что замыкания — это автоматически генерируемые структуры, реализующие определённые трейты, реализовать их самому для своих типов нельзя — по крайней мере, на стабильной версии Rust. Для того, чтобы определить один из Fn*-трейтов для своего типа, нужно активировать две фичи. Первая — fn_traits — позволяет написать определение трейта в обычном виде, а не в засахаренном Fn(Foo) -> Bar, как обычно. Вторая — unboxed_closures — позволяет определять функции с ABI rust-call, которое имеют методы Fn*-трейтов. Если мы их используем, то мы можем сделать то, что невозможно на текущей стабильной версии Rust: перегрузку функции по количеству аргументов. Причина, по которой эти трейты не стабилизированы, видимо, состоит в том, что им в качестве ти́пового параметра требуется не произвольный тип, а кортеж типов аргументов. Это выглядит несколько неловко на фоне отсутствия вариадических обобщённых типов, особенно для функции от одного аргумента — его приходится заключать в одноместный кортеж.

Стоп, в Rust есть одноместный кортеж?!

Да. Он объявляется одинаково на уровне термов и на уровне типов: (x,)

Ужас какой. А что ещё можно сказать про замыкания?

Надо сказать, что замыкания являются, в сущности, обычными типами, которые отличаются в основном анонимностью. И на них, в частности, нужно в некоторых ситуациях накладывать нужные ограничения. Рассмотрим в качестве примера функцию, которая принимает некоторый счётчик и возвращает замыкание, которое инкрементирует этот счётчик на каждый вызов. Для простоты пусть это будет просто u32.  Кажется, что можно написать вот так:

fn make_incrementer(counter: &mut u32) -> impl FnMut() {
    move || *counter += 1
}

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

А разве компилятор не может сам догадаться, как надо?

Нет. Компилятор проверяет правильность расстановки времён жизни, анализируя лишь сигнатуру функции, а не её тело.

Хорошо. Так как нам заставить этот код компилироваться?

Указать явно, что возвращаемое замыкание не может пережить захваченную ссылку. Мы можем сделать это, введя для времени жизни имя и приписав его ссылке и возвращаемому замыканию:

fn make_incrementer<'a>(counter: &'a mut u32) -> impl FnMut() + 'a { // ...

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

fn make_incrementer(counter: &mut u32) -> impl FnMut() + '_ { // ...

Ясно. А для чего там move?

Это связано с тем, как замыкания в Rust работают с захваченными значениями (т. е. со значениями, объявленными снаружи самого замыкания). По умолчанию замыкания захватывают переменные по ссылке (то есть сгенерированный анонимный тип содержит ссылки на эти значения) — мутабельной или иммутабельной, в зависимости от того, как они используются внутри тела замыкания. Использование ключевого слова move переопределяет это поведение по умолчанию и заставляет замыкание захватывать переменные по значению (т. е. перемещает их в замыкание). Если его убрать, то make_counter не будет компилироваться: аргумент counter — фактически, локальная переменная — захватывается по ссылке, время жизни которой ограничено скоупом make_counter, поэтому вернуть такое замыкание за пределы порождающей его функции нельзя.

Так, стоп, так counter захватывается по ссылке или по значению?

В правильном или неправильном варианте?

...В правильном

По значению.

Но...

Просто в данном случае само захватываемое значение является ссылкой.

А, я понял. Кажется...

Ничего, это действительно поначалу немного сбивает с толку.

Что ж, это всё, что ты хотел рассказать про замыкания?

Всё? ВСЁ? АХАХХАХАХХАХХА

О_о

Прошу прощения. В общем, я хотел рассказать про одну продвинутую фичу системы типов Rust...

Так, мне уже это не нравится

...Которая формально не связана с замыканиями, но фактически была введена ради них. Я говорю про higher-ranked trait bounds. В качестве демонстрационного примера я возьму несколько переработанный пример из rustonomicon. Пусть у нас есть структура, в которой лежат какие-то данные и замыкание, которое можно к эти данным применить:

struct Point {
    x: u32,
    y: u32,
    z: u32,
}

struct Closure<F> {
    data: Point,
    func: F,
}

Попробуем написать для Closure метод, который применяет функцию func к point:

impl<F> Closure<F>
where
    F: Fn(&Point) -> &u32,
{
    fn apply(&self) -> &u32 {
        (self.func)(&self.data)
         // ^---- эти скобки необходимы, потому без них это будет означать
         // вызов метода func
    }
}

Пока вроде всё нормально, но мы знаем, что в данном случае Rust вывел времена жизни за нас, в том числе и в ограничении на F. Как это выглядит в развёрнутом виде? Попробуем написать:

impl<F> Closure<F>
where
    F: Fn(&'??? Point) -> &'??? u32,
{
    fn apply<'a>(&'a self) -> &'a u32 {
        (self.func)(&self.data)
    }
}

Непонятно, что писать вместо ???: тут должно быть какое-то время жизни, но мы не можем написать 'a, потому что это время жизни объявлено на методе, а не на impl-блоке целиком. Собственно, снаружи это время жизни 'a может быть, в сущности, любым, его выбирает вызывающий код. Нам нужно как-то выразить тот факт, что F реализует трейт функции с произвольным временем жизни, а не каким-то фиксированным жизни. Higher-ranked trait bounds aka HRTB (ограничение трейтов высшего ранга) позволяют выразить именно это:

impl<F> Closure<F>
where
    F: for<'a> Fn(&'a Point) -> &'a u32
// далее без изменений

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

А почему первый пример не требовал этой страхолюдины?

На самом деле требовал, просто это очередной синтаксический сахар: для ограничений Fn*-трейтов Rust подставляет HRTB автоматически, при этом он следует обычным правилам lifetime elision.

А можно в for использовать тип, а не время жизни?

Увы, нет.

Ясно. А есть пример, когда этот синтаксический сахар ломается?

Ну, он ломается примерно тогда же, когда ломается lifetime elision. Скажем, если взять example_hof из вот этого моего поста и попробовать переписать его на Rust, то в лоб это сделать не удастся:

fn example_hof<F>(n: u32, s: &str, func: F) -> &str
where
    F: FnOnce(&str, &str) -> &str,
{
    let n = n.to_string();
    func(&n, s)
}

На этот код ругается компилятор, причём примерно так же, как на функцию с сигнатурой fn(&str, &str) -> &str:  здесь не хватает информации о том, как результат F зависит от её аргументов. Один из способов поправить этот код — переписать ограничение так:

F: for<'a> FnOnce(&str, &'a str) -> &'a str,

Но здесь вроде можно обойтись без это higher-ranked хренотени, добавив `'a` в число обобщённых параметров `example_hof`

Конечно. Да и лайфтаймы можно расставить по другому. Но в других, более сложных, случаях обойтись без HRTB невозможно.

Так что же, эти HRTB ограничены одними лишь замыканиями?

Отнюдь. Например, в библиотеке serde есть трейт Deserialize<'de> и DeserializeOwned. Первый трейт параметризован временем жизни входных данных 'de, его реализуют типы, которые заимствуют из входа (скажем, строки) какие-то данные. Второй же, как следует из его названия, реализуется типами, которые не заимствуют данные из входа и являются владеющими. Очевидно, если тип реализует DeserializeOwned, то он реализует и Deserialize<'de>, причём для произвольного 'de. И действительно, DeserializeOwned объявлен следующим образом:

pub trait DeserializeOwned: for<'de> Deserialize<'de> { }

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

fn example_hof<F>(n: u32, s: &str, func: for<'a> fn(&str, &'a str) -> &'a str) -> &str;

Фух, это было довольно много. Это всё?

Да. Во всяком случае, пока что.

Спасибо, после общения с тобой я чувствую себя... Мудрее.

Что, правда?

Нет, конечно, лол

Ну и зараза

#..#
#.##
###.

0..1
0.21
000.

[ 0 | 1 | 2 ]
      ^   |
      |   |
      \---/

[ 0 | 1 | 2 ]
  ^       |
  |       |
  \-------/

#prog #моё

НЕ ЧИТАЙТЕ, ЕСЛИ ВЫ ЕЩЁ НЕ РЕШАЛИ СЕГОДНЯШНЮЮ ЗАДАЧУ AUGUST LEETCODING CHALLENGE, НО ХОТИТЕ РЕШИТЬ ЕЁ САМИ

А вот в сегодняшней задаче union-find таки пригодилась. В задаче дан массив чисел, и требуется для графа, в котором вершинами являются числа из этого массива, а рёбра соединяют числа, не являющиеся взаимно простыми, найти размер наибольшей (по числу вершин) связной компоненты. Я, конечно, сначала сделал поиск в глубину, но тест на наличие ребра оказался довольно дорогим даже при предварительном разложении чисел на множители, что приводило к тому, что мои решения отваливались по таймауту на больших тесткейсах (100 000 чисел в диапазоне от 1 до 20 000). Объединение чисел по общему простому множителю в разложении дало куда более хорошую асимптотику и, как следствие, производительность. Единственное, на что нужно было обратить внимание при решении — это изменить процедуру union так, чтобы она возвращала размер вновь образованного множества (естественно, в этом случае нужно объединение по размеру, а не по рангу) и своевременно обновлять текущее максимальное значение.

https://twitter.com/derarto/status/1299926574028992514
(thanks @teamerlin)

Хочется найти новую работу, но на hh и linkedin предлагают работать администратором БД в Пятёрочке или двигать формочки на электроне за 2 косаря в месяц? Можешь зайти на @profunctor_jobs, там публикуют нормальные вакансии, которых больше нет нигде.

Пост проплачен обитателями Нибиру