DS
Ну это называется обычно персистентный иммутабельный список
Size: a a a
2020 April 10
СД
токсик пати детектед
EG
LinkedList<Rc<Value>>
struct Value {
List(LinkedList<Rc<Value>>>),
Number(i32),
String(String),
...
}
struct Value {
List(LinkedList<Rc<Value>>>),
Number(i32),
String(String),
...
}
Примерно так, только сложнее и более общее
P
что значит "ветвится?"
лол
p
лол
кек
P
indeed
EG
Например, в моей версии длина списка известна в каждый момент
EG
LinkedList<Rc<Value>>
struct Value {
List(LinkedList<Rc<Value>>>),
Number(i32),
String(String),
...
}
struct Value {
List(LinkedList<Rc<Value>>>),
Number(i32),
String(String),
...
}
Подожди, нет, твоя версия тоже не разветвленная
Тебе придется клонировать все Rc, чтобы склонировать список
Тебе придется клонировать все Rc, чтобы склонировать список
EG
А мне нужно всего один
p
Подожди, нет, твоя версия тоже не разветвленная
Тебе придется клонировать все Rc, чтобы склонировать список
Тебе придется клонировать все Rc, чтобы склонировать список
ну да
p
А мне нужно всего один
хрень какая-то
EG
хрень какая-то
?
p
список ветвящийся
EG
Обоснуй
Ты получил иммутабельный список, который копируется за O(N)
Я получил иммутабельный список, который копируется за O(1)
Ты получил иммутабельный список, который копируется за O(N)
Я получил иммутабельный список, который копируется за O(1)
EG
Хрень — твой список, а не мой
EG
let a = list![1, 2, 3];
let b = a.cons(4);
let c = a.cons(5);
let b = a.cons(4);
let c = a.cons(5);
4 → 3 → 2 → 1
5 →↑
Эта структура в памяти выглядит так
EG
На элемент (3) указывают два элемента, и дальше это всё равно, что один список
p
я же говорю, хрень какая-то бесполезная
EG
я же говорю, хрень какая-то бесполезная
Основа функциональных языков, но ладно
EG
Собственно, встроенный список Haskell — это, вероятно, оно