Hacker News Reader

Comment by kbp | Hacker News Reader

> Complicated pointer-type data structures like linked lists

If a singly linked list is a complicated data structure then what's a simple one?

A heap would be simple.

Rust's ownership rules make it hard to implement data structures composed of nodes that own references to other nodes. (This includes linked lists, binary trees, and naive implementations of graphs.) There is a reason for this - it's rather tricky to implement such data structures truly safely in any language without introducing hidden assumptions, that's why they are so frequently seen in interview questions for java and c++ coders.

The difficulty of such interview questions doesn't stem from the problem of ensuring memory safety, but stuff like "finding the form of the recursion you need".

It's complicated because it's self-referential, not because it's conceptually complicated. Self-referential data structures in rust are more difficult because of the way ownership works.

Of course, self-referential, mutating data structures are nefarious and hard to build in a thread-safe way. So the extra difficulty is actually an symptom of the inherit complexities of making them thread-safe.

There aren't really simple data structures that involve pointers. Pointers are just hard (where hard means they require programmers to hold state in their head), and rust makes that explicit.

The reality is that implementing data structures that require pointers is not a typical task, and they're ideally provided by the stdlib or crates.

An article you might find helpful is this one on why imperative algorithms are harder to mathematically verify than functional ones:

https://semantic-domain.blogspot.com/2018/04/are-functional-...

You don't need to be a mathematician to follow it with this excerpt summarizing its key point:

"The difficulty of imperative programming arises from the combination of state, aliasing and procedure calls. Any two of these features can be handled without that much difficulty, but the combination of all three effectively makes reasoning (nearly) as difficult as correct concurrent programming. "

The garbage-collected languages let you ignore the aliasing problems with a performance penalty. Rust in safe mode without GC forces you to (a) deal with it and (b) deal with it in a way that works for all inputs (type/memory safety). That usually requires mathematical verification using tools such as separation logic. Rust's method is much easier to use with tradeoff of limitations on expressing code in certain ways.

Folks that get along with the borrow-checker say it helps to design the program around data and easy methods of using it versus starting with control flow forcing it on a data structure. I'll also add that linked lists are inherently hard to get right on all inputs regardless of low-level language. They're actually a popular way to test new, mathematical methods for specifying and proving algorithms correct. Fortunately, Rust folks have a goto write-up on linked lists in their language:

https://cglab.ca/~abeinges/blah/too-many-lists/book/

in comparison to a vector yes it's complex.

it's recursive. it has pointers. algorithms to work with one aren't trivial and often are destructive.

Anything that doesn't involve aliased pointers will be simpler from a safety perspective.

Lists, stacks, queues, hashtables. Maybe btrees.

An array?

Hashmap or array :)

Hard to imagine a hashmap is less complicated than a singly linked list under the hood.

From a memory management perspective, a probing hashmap is just a vector/array. All of the bookkeeping is "safe" from a memory perspective.

A hashmap is in its simplest form just an array.

They're roughly equal if the singly-linked list is just a head pointer, because the "each object is only reachable through a single path, which owns it" property means the compiler can reason about what's going on. It's when you add a tail pointer (or go whole hog and make it doubly-linked) that you lose that property and have to use unsafe code (or heavyweight things like Arc<Mutex<...>>) to get the compiler off your back.

Reply on news.ycombinator.com