Comment by rahkiin
2 years ago
And cannot have linked lists either. When you make a compiler in rust, basically you give everything the same lifetime and drop the memory at the very end. That allows cicular references. Or you use Rc, but that is against what purists want you to do. For longer lifetime programs with complex models the borrow checker becomes harder
You can express linked lists efficiently in Rust using the GhostCell/QCell pattern. Yes it's clunky, but this is after all an area of active research in PL theory. As it is, most ordinary "easy" implementations of linked lists do not actually prove memory safety - it's a genuinely non-trivial problem, not a case of mere incidental complexity.