Hacker News Reader

Hacker News

Comment by worik | Hacker News Reader

Full thread

worik

> Now suppose we want to add a parent link to every node.

Don't.

You do not need to.

Rust does stop you creating self referential structures (easily)

In the case of a binary tree that is not a problem

There might exist some specialised case where there is no more memory to allocate at run time, but in the common case it is more efficient in every respect to use algorithms with your data structures and dispense with back links

I have been working on a C program built by a (mostly brilliant) programmer that put back links in every structure (parent links in trees, doubly linked lists) and the waste of resources, in a constrained environment, is frustrating

Just don't

View on HN

Some algorithms need the parent or bidirectional pointers.

If the language doesn’t let you then the language sucks.

This post shows 3 ways of doing it, including essentially the same way you'd do it in C. And it's exactly as dangerous as doing it in C is, but at least you can isolate that dangerous code to one part of your code base.

> you can isolate that dangerous code to one part of your code base.

This is the whole point for me. There are loads of reasons fundamental data structures want to use behaviour the compile can't prove is sound, but humans can burn time discussing, proving the algorithms and testing the implementation. Then, you ask the compiler to prove all the simple glue stuff on top.

I suspect there's a type theory here where many cases of parent links essentially represent the exact same problem, and if you solve one, you can restate most/all of the others in this form and then it's proven too.

You know that popcount bit counting device that treats a word of memory as a short SIMD instruction using the 32 or 64 bit ALU? I learned recently that compilers can detect that and emit popcount instructions if those are faster on the target architecture.

I suspect if you can detect that, you could detect a safe parental reference device and let it pass the checker.

> Some algorithms need the parent or bidirectional pointers.

For trees some, not very good, algorithms require parent pointers

I think it's best to think of this as a good toy example, and not get caught up in the specific utility of a "parent" node.

It is just a bad example.

One of the main points is that there are very few algorithms that require back links that create cycles.

Cyclic data structures, rare as they are, are also hard to reason about. Even for garbage collectors!

If you have to implement one in Rust (I have) it is a bother, a big hassle.

It is a good thing that in the general case when a programmer is implementing back links they are doing the Wrong Thing.

Reply on news.ycombinator.com