list inversion
Jan. 5th, 2023 03:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoА вот задачу инвертирования списка я считаю очень и очень полезной для понимания Rust'а. Ощупывание границ того, что можно делать с deconstructed structs - это очень и очень важно.
Об алгоритме.
Есть два алгоритма:
1) Сложить всё в стек и собрать обратно список в другом порядке. При том, что алгоритмически это такой же уровень сложности, на практике - это ~30-кратное замедление из-за необходимости иметь дополнительные аллокации и копирования.
2) Пройти по списку и поменять направление ссылок. Было (val1, Link_to_2) -> (val2, Link_to_2) -> (val3, None), должно стать (val1, None) <- (val2, Link_to_1) <- (val3, Link_to_2).
В условиях указателей (си-подобный язык) эта задача довольно простая, потому что мы казуально допускаем, что в какой-то момент у нас "всё висит" или есть два указателя на одно и то же место. (ну и чё такого?).
В Rust же всё куда более интригующе. Список - это
При этом настоящий тип списка - это
Проговорим это:
Список это:
Либо None
Либо enum, который владеет smart pointer'ом на heap, у которого тип Box, внутри которого находится структура ListNode.
Структура ListNode владеет val и next, который и есть остаток списка.
Чувствуете, как всё нюасно стало? Не ссылки, а есть владение. Чтобы взять содержимое val или next мы должны:
1. Деконструировать Option.
2. Деконструировать ListNode.
После того, как мы деконструировали или Option, или ListNode, мы больше не можем передать его куда-то дальше!
То есть наивное: something.next = cur мы не можем сделать! У нас cur больше не существует.
В целом, эта задача была бы не решаема, если бы не возможность "реконструировать" ListNode. Если мы для каждого поля, из которого мы "взяли" значения положим назад значения (move, передадим владение туда), то мы получим "реконтструированную" структуру, которую мы можем передавать дальше.
Деконструированный же Option невозможно реконструировать (его больше нет), вместо этого мы можем создать новый. Что такое "новый Option" и чем он отличается от старого? В целом, ни чем. Я даже не уверен, что это создаст какие-то машинные инструкции, но с точки зрения компилятора новый Some и старый Some (который мы деконструировали) - две совершенно разные вещи.
Вот решение:
Проговариваю его по шагам:
Мы деконструируем head (если есть что деконструировать), и создаём переменную node, которая получает владением над содержимым head. Option<Box<ListNode>> → Box<ListNode>.
node имеет тип Box - это умный указатель на кучу, который (за вычетом кучи) просто владеет ListNode.
К этому моменту у нас head не имеет значения (мы делали move из него в строчке while let).
Мы передаём в head значение поля node.next. В этот момент node становится частично деконструированной. next из неё забрали, а value всё ещё принадлежит node.
После этого мы перемещаем в node.next значение из prev. prev перестаёт иметь какое-либо значение (т.к. отдал владение значением). Зато node теперь полностью сконструирован, потому что он владеет всеми своими значениями.
Мы создаём новое значение Some(node), забирая значение из переменной node, node перестаёт иметь какое-либо значение (т.к. отдал владение значением в Some), после чего мы отдаём владение Some(node) переменной prev.
К концу цикла у нас: prev - содержит в себе Some(node), next содержит в себе либо None, либо Some со следующим элементом списка, то есть содержит остаток списка), node - не определён. Цикл заканчивается, у node заканчивается область видимости и она (он? оно?) уничтожается. Т.к. значение уже было move, то ничего делать не надо. Начинается следующая итерация.
В конце мы отдаём владение prev, внутри которого владение prev.next, внутри которого prev.next.next и т.д., то есть инвертированный список.
Вот, примерно так устроен процесс думания о Rust программе. Где-то тут был пропущен вопрос, как мы сквозь Box<ListNode> получаем поля ListNode. Я тщательно этот вопрос не продумывал, но насколько я понимаю, это неявно вызываемые функции deref и deref_mut, реализованные через трейты Deref и DeferMut.
Об алгоритме.
Есть два алгоритма:
1) Сложить всё в стек и собрать обратно список в другом порядке. При том, что алгоритмически это такой же уровень сложности, на практике - это ~30-кратное замедление из-за необходимости иметь дополнительные аллокации и копирования.
2) Пройти по списку и поменять направление ссылок. Было (val1, Link_to_2) -> (val2, Link_to_2) -> (val3, None), должно стать (val1, None) <- (val2, Link_to_1) <- (val3, Link_to_2).
В условиях указателей (си-подобный язык) эта задача довольно простая, потому что мы казуально допускаем, что в какой-то момент у нас "всё висит" или есть два указателя на одно и то же место. (ну и чё такого?).
В Rust же всё куда более интригующе. Список - это
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>
}
При этом настоящий тип списка - это
Option<Box<ListNode>>
Проговорим это:
Список это:
Либо None
Либо enum, который владеет smart pointer'ом на heap, у которого тип Box, внутри которого находится структура ListNode.
Структура ListNode владеет val и next, который и есть остаток списка.
Чувствуете, как всё нюасно стало? Не ссылки, а есть владение. Чтобы взять содержимое val или next мы должны:
1. Деконструировать Option.
2. Деконструировать ListNode.
После того, как мы деконструировали или Option, или ListNode, мы больше не можем передать его куда-то дальше!
То есть наивное: something.next = cur мы не можем сделать! У нас cur больше не существует.
В целом, эта задача была бы не решаема, если бы не возможность "реконструировать" ListNode. Если мы для каждого поля, из которого мы "взяли" значения положим назад значения (move, передадим владение туда), то мы получим "реконтструированную" структуру, которую мы можем передавать дальше.
Деконструированный же Option невозможно реконструировать (его больше нет), вместо этого мы можем создать новый. Что такое "новый Option" и чем он отличается от старого? В целом, ни чем. Я даже не уверен, что это создаст какие-то машинные инструкции, но с точки зрения компилятора новый Some и старый Some (который мы деконструировали) - две совершенно разные вещи.
Вот решение:
pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
let mut prev = None;
while let Some(mut node) = head{
head = node.next;
node.next = prev;
prev = Some(node);
}
prev
}
Проговариваю его по шагам:
Мы деконструируем head (если есть что деконструировать), и создаём переменную node, которая получает владением над содержимым head. Option<Box<ListNode>> → Box<ListNode>.
node имеет тип Box - это умный указатель на кучу, который (за вычетом кучи) просто владеет ListNode.
К этому моменту у нас head не имеет значения (мы делали move из него в строчке while let).
Мы передаём в head значение поля node.next. В этот момент node становится частично деконструированной. next из неё забрали, а value всё ещё принадлежит node.
После этого мы перемещаем в node.next значение из prev. prev перестаёт иметь какое-либо значение (т.к. отдал владение значением). Зато node теперь полностью сконструирован, потому что он владеет всеми своими значениями.
Мы создаём новое значение Some(node), забирая значение из переменной node, node перестаёт иметь какое-либо значение (т.к. отдал владение значением в Some), после чего мы отдаём владение Some(node) переменной prev.
К концу цикла у нас: prev - содержит в себе Some(node), next содержит в себе либо None, либо Some со следующим элементом списка, то есть содержит остаток списка), node - не определён. Цикл заканчивается, у node заканчивается область видимости и она (он? оно?) уничтожается. Т.к. значение уже было move, то ничего делать не надо. Начинается следующая итерация.
В конце мы отдаём владение prev, внутри которого владение prev.next, внутри которого prev.next.next и т.д., то есть инвертированный список.
Вот, примерно так устроен процесс думания о Rust программе. Где-то тут был пропущен вопрос, как мы сквозь Box<ListNode> получаем поля ListNode. Я тщательно этот вопрос не продумывал, но насколько я понимаю, это неявно вызываемые функции deref и deref_mut, реализованные через трейты Deref и DeferMut.
no subject
Date: 2023-01-05 02:55 pm (UTC)Спасибо за разъяснения. У меня все больше растет ощущение, что с растом что-то принципиально не так. Ну, линейная логика это хорошо, но вот интуиционизма не хватает. Правильных монад.
no subject
Date: 2023-01-05 03:10 pm (UTC)Ощущение, что "что-то не так" возникает в тот момент, когда Rust отвергает корректные программы. Ты (программист) знаешь, что это корректно, а компилятор тебе не верит.
Но, на самом деле, ровно то же самое происходило и в момент появления языков высокого уровня. Я, программист, знаю, что внутри этих байтов находится указатель на код и я хочу туда сделать jmp, по вот этому указателю. А мне язык не даёт это сделать, потому что я ему не доказал, что это можно.
То самое (в меньшем объёме, потому что есть type casting), происходит и с обычной типизацией. Я знаю, что содержимое этого int'а - это валидная строка. Компилятор, (char*) его!
В целом, то же самое сейчас происходит в с владением и lifetimes. Взамен на обещание радужных крабов язык отвергает целые классы ранее вполне себе работающих программ. Вместе с ними отвергаются массовые странные глюки (use after free, type aliasing, etc), и радужные крабы танцуют.
Я не знаю как у хаскеля реализованы ссылки (особенно &mut), подозреваю, что никак.
Я нашёл вот это, не читал. Но упоминание Rust во вступлении в какую-то хаскелёвую монаду порадовало.
https://ir.library.oregonstate.edu/downloads/g732dg05w
no subject
Date: 2023-01-05 03:24 pm (UTC)Охренеть. The Ownership Monad. Если этот вопрос решен, и все получается выразить в интуиционизм, то вот и славненько.
Я-то не имел в виду, что раст плохой, я имел в виду, что он еще недоразвит - или его понимание недоразвито.
no subject
Date: 2023-01-07 12:46 pm (UTC)Я не сварщик, я только PDF'ку нашёл.
У Rust'а главное, что есть - это понимание системности. В Haskell нет стека (насколько я понимаю), и семантической разницы между stack allocated и heap allocated нет. (Если я ошибаюсь, извини, я пересказываю как мне в голову про хаскель напели). А в Rust есть, и оно выражается через доступные типы. Это с одной стороны слегка усложняет рассуждения, с другой стороны, эти усложнённые рассуждения дают очень много пользы за пределами очень-очень-быстро (например, предотвращают целые классы ошибок).
Ну и для меня, субъективно, главное, что за вычетом зауми в районе GAT'ов, всё, что делает Rust остаётся объяснимым с точки зрения компьютера (как вычислителя). Категории не про компьютеры, так что любое объяснение там быстро сваливается в семигрупоиды и стрелки.
no subject
Date: 2023-01-07 01:23 pm (UTC)Ну в целом да, Rust, с практической стороны, придуман, чтобы хардвер не мучать, а употреблять научно; а с теоретической стороны там внутре линейная логика. Я не большой фанат линейной логики (алхимия в ней тоже выражается вполне логично), но ценю. А вот с комбинацией, с линейным интуиционизмом, я не знаком. А жаль. Монады имеют большой смысл в смысле выразительности.
no subject
Date: 2023-01-07 02:57 pm (UTC)В rust'е типы не линейные, а афинные. Ты можешь в любой момент выкинуть значение и не юзать его.
Есть даже костыль #[must_use], который превращает афинный тип в линейный.
Кроме того, поверх афинных типов добавляются ссылки, после чего типы превращаются в шути-что, включая inner mutability (когда объект можно менять по немутабельной ссылке).
no subject
Date: 2023-01-07 03:31 pm (UTC)А! Спасибо. Не в курсе был.
no subject
Date: 2023-01-05 05:07 pm (UTC)no subject
Date: 2023-01-07 12:49 pm (UTC)Ну, я, кстати, не уверен, что спискам так уж надо unsafe. Option Box - вполне себе хорошо оптимизируемая комбинация. Скорее, тут можно говорить о том, что список - это глупо. Уж лучше подобие B-tree (но для списка). Кстати, я погуглил, я не знаю как такая структура называется.
no subject
Date: 2023-01-09 10:41 am (UTC)no subject
Date: 2023-01-09 10:54 am (UTC)Когда я искал вопросы/ответы, я наткнулся на тредик на SO, где товарищи говорили, что Rc/RefCell - это code smell в rust'е для деревьев, т.к. выглядит как попытка обойти нормальные правила владения.
no subject
Date: 2023-01-09 10:58 am (UTC)Я собственно хотел только одно сказать: что если ты имплементируешь generic структуру данных, тебе не обязательно прикладывать отдельные усилия чтобы избежать unsafe, так как unsafe как раз создан для такого низкоуровневого кода.
no subject
Date: 2023-01-09 11:04 am (UTC)Я смотрю crust of rust (где как раз примеры использования unsafe для реализации структур данных показываются), и мне очень грустно, потому что в unsafe нужно обладать каким-то особым строением мозга, чтобы про происходящее рассуждать во всей совокупности.
Наверное, с miri/prusti это будет проще, но в одиночку в unsafe я себя чувствую почти как в C. Шаг в лево/шаг в право, и некуда больше ходить, потому что кто-то валенок на пульт бросил.
no subject
Date: 2023-01-09 11:10 am (UTC)no subject
Date: 2023-01-09 11:18 am (UTC)Да. И есть вариант такое писать, или вариант такое не писать. Если можно обойтись без болгарки, я предпочитаю без болгарки.
В какой-то момент времени, да, возникает необходимость (я вот с интересом узнал про xored double linked list вчера, мне страшно представить себе процесс написания такого на rust), но если можно избежать, лучше избегать.