4 ms·

In Haskell and other purely functional programming languages, one encounters exactly the same challenge. These communities have worked out sophisticated, well-d

In Haskell and other purely functional programming languages, one encounters exactly the same challenge. These communities have worked out sophisticated, well-documented solutions. Facing any problem, one should always ask "Who else has already encountered this problem?" To ignore their work is to reinvent the wheel. As a Haskell programmer exploring Rust, I was thrilled to recognize this parallel. One gains persistent data structures. In many problems, "reuse" is far more efficient than carving out each new instance from scratch. I've never understood the evangelists that claim one can't learn functional programming after any exposure to conventional programming, but perhaps the prejudices run deeper than I've recognized. How does one characterize a rejection out-of-hand of persistent data structures? "One-use plastic bag syndrome"

throwvirtever 5y ago
Looking for precedents is always good advice, but the essential issue is that even if you don't re-invent the wheel, the "wheel" that works in functional programming territory, for certain tasks (e.g. the binary tree with parent pointers), is more complicated, more verbose, and comes with downsides. People ignore existing work (at least at first), and assume they can make it simpler themselves, because they're surprised it _needs_ to be sophisticated. EDIT: That said, the article does a great job of explaining the problems and the potential solutions.
helen___keller 5y ago
I come from a functional background (significant work in SML and Ocaml) and went into learning Rust excited to implement all my favorite persistent data structures, only to find myself foiled by borrow and lifetime madness similar to what’s described in the naive implementation in the OP. Where I could define a simple tree in one line of SML, I struggled to define one at all in Rust! (I think my problem actually just came down to the lifetime on the object holding the tree itself and the way I was instantiating nodes; but when those lifetime compiler warnings popped up my eyes would glaze over and I knew it was time to put rust down for the day) I imagine Haskell programmers have a step up because the Monad system is significantly less forgiving than SML’s look-the-other-way approach to side effects, and in this sense Haskell and Rust are more similar than many other functional languages.
kubb 5y ago
Is it possible that you might be misunderstanding the "challenge" being faced here? In Rust the "problem" is that the safe subset of the language enforces ownership rules, which make directly representing circular pointer structures impossible. Of course, you can use "unsafe" and it becomes as simple as in C. This tradeoff is well known since the inception of Rust. In Haskell, the "problem" is that all functions need to be pure, so if you need to mutate a data structure, you actually have to create a new instance, sharing the bulk of the structure of the previous instance to be efficient. This is not the same thing, but you seem to think it is. In Rust, persistent data structures still use reference counting to manage lifetime of the objects inside the structure (see rpds), which is also what one of the solutions listed here does.
- nickkell 5y ago
  I thought maybe Haskell also prohibited circular references, but looking it up they do something called “tying the knot”, which is enabled by the language’s laziness
  - solomatov 5y ago
    You can't tie the knot in Rust. Tying the knot creates a self referential structure, which creates an ownership loop.
- juxtapose 5y ago
  > This is not the same thing, but you seem to think it is. They are only different superficially. The deeper problem here is they both assume that "a new, valid value can only reference old, existing values". (For the sake of simplicity, let's pretend Haskell does not have laziness for a moment.) This is reasonable in almost any language because it enables easy inductive reasoning. Rust forbids circular references exactly for this reason, the whole borrow check builds on this principle: a new pointer becomes invalid when the old pointer becomes invalid. You cannot create them in Haskell either due to this very reason, if there is no laziness. Techniques in Haskell, like tying the knot, work just because laziness makes it possible to reference values in the future. Unfortunately, it also creates possibilities for bottoms, which renders it unusable for a sound proof system -- Rust cannot do the same thing because borrow check should be sound and terminating. It's easy in C++ because C++ does not guarantee validity of objects. You know, NULL is _always_ an invalid pointer. Rust and Haskell both guarantee that a constructed object is always valid. (ofc, only in most cases where the escape hatches are not used.)

throwvirtever 5y ago

Looking for precedents is always good advice, but the essential issue is that even if you don't re-invent the wheel, the "wheel" that works in functional programming territory, for certain tasks (e.g. the binary tree with parent pointers), is more complicated, more verbose, and comes with downsides. People ignore existing work (at least at first), and assume they can make it simpler themselves, because they're surprised it _needs_ to be sophisticated. EDIT: That said, the article does a great job of explaining the problems and the potential solutions.

helen___keller 5y ago

I come from a functional background (significant work in SML and Ocaml) and went into learning Rust excited to implement all my favorite persistent data structures, only to find myself foiled by borrow and lifetime madness similar to what’s described in the naive implementation in the OP. Where I could define a simple tree in one line of SML, I struggled to define one at all in Rust! (I think my problem actually just came down to the lifetime on the object holding the tree itself and the way I was instantiating nodes; but when those lifetime compiler warnings popped up my eyes would glaze over and I knew it was time to put rust down for the day) I imagine Haskell programmers have a step up because the Monad system is significantly less forgiving than SML’s look-the-other-way approach to side effects, and in this sense Haskell and Rust are more similar than many other functional languages.

kubb 5y ago

Is it possible that you might be misunderstanding the "challenge" being faced here? In Rust the "problem" is that the safe subset of the language enforces ownership rules, which make directly representing circular pointer structures impossible. Of course, you can use "unsafe" and it becomes as simple as in C. This tradeoff is well known since the inception of Rust. In Haskell, the "problem" is that all functions need to be pure, so if you need to mutate a data structure, you actually have to create a new instance, sharing the bulk of the structure of the previous instance to be efficient. This is not the same thing, but you seem to think it is. In Rust, persistent data structures still use reference counting to manage lifetime of the objects inside the structure (see rpds), which is also what one of the solutions listed here does.

nickkell 5y ago
I thought maybe Haskell also prohibited circular references, but looking it up they do something called “tying the knot”, which is enabled by the language’s laziness
- solomatov 5y ago
  You can't tie the knot in Rust. Tying the knot creates a self referential structure, which creates an ownership loop.
juxtapose 5y ago
> This is not the same thing, but you seem to think it is. They are only different superficially. The deeper problem here is they both assume that "a new, valid value can only reference old, existing values". (For the sake of simplicity, let's pretend Haskell does not have laziness for a moment.) This is reasonable in almost any language because it enables easy inductive reasoning. Rust forbids circular references exactly for this reason, the whole borrow check builds on this principle: a new pointer becomes invalid when the old pointer becomes invalid. You cannot create them in Haskell either due to this very reason, if there is no laziness. Techniques in Haskell, like tying the knot, work just because laziness makes it possible to reference values in the future. Unfortunately, it also creates possibilities for bottoms, which renders it unusable for a sound proof system -- Rust cannot do the same thing because borrow check should be sound and terminating. It's easy in C++ because C++ does not guarantee validity of objects. You know, NULL is _always_ an invalid pointer. Rust and Haskell both guarantee that a constructed object is always valid. (ofc, only in most cases where the escape hatches are not used.)