История изменений

Да пипец нерешаемая задача про двусвязный список. Его сила в том, что ты можешь отдать клиенту ссылку на элемент и от неё клиент сможет плясать. Тогда вставка даже в середину списка будет O(1). Но проблема в том, что если у тебя вчера был элемент списка, то завтра он может перестать им быть, например, благодаря удалению диапазона. Поэтому такой список, чтобы быть безопасным, должен иметь указателя на сам объект «список» в каждом элементе, и при каждой модификации этот указатель нужно обновлять. И тогда это уже не двусвязный список, а нечто иное. Или нужно как-то ещё гарантировать, что на момент попытки действия над элементом списка мы будем точно знать, находится ли элемент в списке или нет. Но я такого себе даже представить не могу (в смысле статического доказательства).

Я для себя вывод сделал такой, что я попробую проработать сочетание RC + GC, как это уже сделано в Питоне. И соответственно дальше мне уже неинтересно выяснять, как это делается на Расте. Вариант создавать структуры данных на «unsafe» подъязыке, который может промазать мимо памяти, меня совершенно не интересует. А элементы Раста в Обероне уже и так есть, там есть var параметры, которые чем-то похожи на времена жизни в Расте (хотя не полностью, но всё же как-то похожи).

Да пипец нерешаемая задача про двусвязный список. Его сила в том, что ты можешь отдать клиенту ссылку на элемент и от неё клиент сможет плясать. Тогда вставка даже в середину списка будет O(1). Но проблема в том, что если у тебя вчера был элемент списка, то завтра он может перестать им быть, например, благодаря удалению диапазона. Поэтому такой список, чтобы быть безопасным, должен иметь указателя на сам объект «список» в каждом элементе, и при каждой модификации этот указатель нужно обновлять. И тогда это уже не двусвязный список, а нечто иное. Или нужно как-то ещё гарантировать, что на момент попытки действия над элементом списка мы будем точно знать, находится ли элемент в списке или нет. Но я такого себе даже представить не могу (в смысле статического доказательства).

Я для себя вывод сделал такой, что я попробую проработать сочетание RC + GC, как это уже сделано в Питоне. И соответственно дальше мне уже неинтересно выяснять, как это делается на Расте. А элементы Раста в Обероне уже и так есть, там есть var параметры, которые чем-то похожи на времена жизни в Расте (хотя не полностью, но всё же как-то похожи).

Да пипец нерешаемая задача про двусвязный список. Его сила в том, что ты можешь иметь ссылку на элемент и от неё плясать. Тогда вставка даже в середину списка будет O(1). Но проблема в том, что если у тебя вчера был элемент списка, то завтра он может перестать им быть, например, благодаря удалению диапазона. Поэтому такой список, чтобы быть безопасным, должен иметь указателя на сам объект «список» в каждом элементе, и при каждой модификации этот указатель нужно обновлять. И тогда это уже не двусвязный список, а нечто иное. Или нужно как-то ещё гарантировать, что на момент попытки действия над элементом списка мы будем точно знать, находится ли элемент в списке или нет. Но я такого себе даже представить не могу (в смысле статического доказательства).

Я для себя вывод сделал такой, что я попробую проработать сочетание RC + GC, как это уже сделано в Питоне. И соответственно дальше мне уже неинтересно выяснять, как это делается на Расте. А элементы Раста в Обероне уже и так есть, там есть var параметры, которые чем-то похожи на времена жизни в Расте (хотя не полностью, но всё же как-то похожи).

Да пипец нерешаемая задача про двусвязный список. Его сила в том, что ты можешь иметь ссылку на элемент и от неё плясать. Тогда вставка даже в середину списка будет O(1). Но проблема в том, что если у тебя вчера был элемент списка, то завтра он может перестать им быть, например, благодаря удалению диапазона. Поэтому такой список, чтобы быть безопасным, должен иметь указателя на сам объект «список» в каждом элементе, и при каждой модификации этот указатель нужно обновлять. И тогда это уже не двусвязный список, а нечто иное. Или нужно как-то ещё гарантировать, что на момент попытки действия над элементом списка мы будем точно знать, находится ли элемент в списке или нет. Но я такого себе даже представить не могу.

Я для себя вывод сделал такой, что я попробую проработать сочетание RC + GC, как это уже сделано в Питоне. И соответственно дальше мне уже неинтересно выяснять, как это делается на Расте. А элементы Раста в Обероне уже и так есть, там есть var параметры, которые чем-то похожи на времена жизни в Расте (хотя не полностью, но всё же как-то похожи).

Да пипец нерешаемая задача про двусвязный список. Его сила в том, что ты можешь иметь ссылку на элемент и от неё плясать. Тогда вставка даже в середину списка будет O(1). Но проблема в том, что если у тебя вчера был элемент списка, то завтра он может перестать им быть, например, благодаря удалению диапазона. Поэтому такой список, чтобы быть безопасным, должен иметь указателя на родительский список, и при каждой модификации этот указатель нужно обновлять. И тогда это уже не двусвязный список, а нечто иное. Или нужно как-то ещё гарантировать, что на момент попытки действия над элементом списка мы будем точно знать, находится ли элемент в списке или нет. Но я такого себе даже представить не могу.

Я для себя вывод сделал такой, что я попробую проработать сочетание RC + GC, как это уже сделано в Питоне. И соответственно дальше мне уже неинтересно выяснять, как это делается на Расте. А элементы Раста в Обероне уже и так есть, там есть var параметры, которые чем-то похожи на времена жизни в Расте (хотя не полностью, но всё же как-то похожи).