Hacker News Reader

The rest of the points here are excellent, but don't use `unsafe` until you have completely internalised the borrow checker rules. If your safe attempt is unsafe (and therefore doesn't pass the borrow checker), your unsafe code will be unsafe too. The only difference is that the unsafe code won't be caught at compile-time.

This is not true, in general. The borrow checker has many limitations where it cannot prove that something is safe, so it assumes it is unsafe. The classic example is borrowing disjoint slices from an array.

The borrow checker has limitations but I agree with gp: if you haven't fully internalized its rules, especially if don't understand why it is yelling at you at some point, then you should not go unsafe because you're most likely going to write memory bugs.

I have to second the use of immutable data structures. That is the style I'd adopted prior to using rust, and in learning Rust I've found that I've hardly ever fought with the borrow checker.

Suggesting unsafe code seems like a bad move, if haven't mastered the borrow checker, is learning the dark magic of unsafe a good plan?

> Apply functional programming idioms and use immutable data structures if you can.

How would you implement efficient and flexible graph algorithms using these techniques? E.g., considering that edges need to be traversed quickly, updated quickly, etc., and graphs are arbitrarily complicated (not just trees or DAGs).

There's a decent amount of research into functional graph algorithms. The right approach depends on the application, but two interesting ones are inductive graphs[1] and zippers[2].

I also agree with other commenters that you should make certain you actually need your arbitrarily complicated graph, though.

[1]: http://web.engr.oregonstate.edu/~erwig/papers/InductiveGraph... [2]: https://www.cs.tufts.edu/~nr/pubs/zipcfg.pdf

Indirect the graph connections. This is almost always a better design anyway. Instead of storing pointers from one graph node to another, give each node an identifier and store a map from identifiers to nodes. Each node then has a set (or other collection) of identifiers it's connected to.

You can use either a mutable or immutable map for this construction.

That's basically the "don't keep references into a Vec, keep indices" advise. I don't really like that because references explicitly encode the dependency in the type system. When you start juggling indices you're basically implementing poor man's malloc. You need to make sure you don't lose track of any of them.

I think owned objects should have lifetimes and a "points to non-moving memory" property. E.g. a vec can be moved and must outlive all the objects that take references from it. That way it would be possible to keep an owned object and refs to it in the same struct and pass the whole bundle around.

> You need to make sure you don't lose track of any of them.

This is a fair point, but note that in any memory management scheme except garbage collected, you run the risk of having a dangling reference if you use direct pointers to other nodes. At least with node identifiers, you can safely check that the other node still exists, in any memory management scheme.

Store your graph as an adjacency matrix, using either a 2D array of edges (if your problem is small enough), or as a sparse matrix (hash table or similar).

Curious: what kind of graph structures do you typically find yourself writing? Maybe I'm just doing different stuff, but I find myself with tree or DAGs in almost all cases.

> there's nothing wrong with [unsafe code]

I suppose I must ask, then: why Rust?

If you keep unsafe code in modules and don't pass raw pointers in between, it is much easier to audit the code. All the glue code is automatically safe. Then each module can be audited separately to make sure it is impossible to make it crash by using public API.

Rust `collections' library is full of unsafe code. Just for example: https://doc.rust-lang.org/src/collections/up/src/libcollecti... But you can never leave a BTree in an invalid state by adding or removing elements. Given safe collections library you can write lots of applications without resorting to unsafe code and having to prove the safety of your code.

Proving safety of B-Trees, threaded code and things like that requires a whole theorem prover that Rust most likely will never provide. You need to use Coq or similar tool if you are developing new algorithms and data structures. But if you are not a pure computer science researcher, most likely you don't need it. All you have to do is to carefully translate pseudocode from paper into Rust and package it.

The point is to contain them and hide them under nice safe abstractions. If you avoid unsafe rust at all costs, including unsafe rust hidden under abstractions, you'll find that you can't write any rust at all because the standard library is so full of unsafe rust.

Instead of using unsafe code, I would use RefCell first: «a mutable memory location with dynamically checked borrow rules»

https://doc.rust-lang.org/std/cell/struct.RefCell.html

Using clone() also often helps. clone() has an overhead since you copy bytes, but sometimes you need to get something working right first, then optimise.

There are other tricks if the borrow checker interferes.

> functional programming idioms

Proper tail recursion was still missing last time I checked. Does it affect functional programming in Rust?

It's rare to actually use tail-recursive algorithms in Rust since those can be written with a loop, which Rust does support.

I mean, it's rare to actually manually recurse in Haskell too, and when you need to, it's often not something you can write tail-recursively.

>it's rare to actually manually recurse in Haskell

I wonder if there is a semi-easy way to measure this. My impression was that while the papers and tutorials are all about combinators, the people writing Haskell "in the wild" tend to go with general recursion more often than you might expect.

Even if you recurse, it doesn't mean you can make it tail-recursive. It might be a style issue, but Rust programmers are just going to use combinators instead anyway since recursion is slower.

It's not guaranteed, though LLVM may do it if it feels like it. We may gain guaranteed TCO in the future, we'll see.

> Apply functional programming idioms and use immutable data structures if you can.

This is what I've tried to do when learning Rust. However, I find it ends up more boilerplatey than a language like Haskell. I had to do lots of clone() and iter(), which cluttered up the functional idioms. Maybe I'm doing it wrong though.

Rust makes deep copies explicit, whereas those languages don't. So if you program in the exact same style, it will be a bit more verbose; Rust is exposing a cost here.

That said, idiomatic Rust does lean a bit more functional than many languages.