RustでImmutable Stackを使おうとした際に遭遇した難しさ

最近下記の記事を読んで、Immutable Stackなるものを知った.
qiita.com

この記事の本質はArc/Rcの仕組みを紐解くところあるのだけれど、Immutable Stackの概念が妙に新鮮かつ(状態を持たずにstackを実現している部分が)とても美しいと思った.

この記事を参考にして、Immutable Stackを普通のプログラミング時に使えないかと思って色々試行錯誤してみたけど、結論あまりうまくできていない.

struct Stack<T>(Option<Rc<(T, Stack<T>)>>)
struct Info {}  

struct User {
    s: Stack<Info>
}

impl User {
   fn pop_info(&mut self) {
       self.s.pop();
       // ...
}

模擬コードはこんな感じで、Userが何かしらのStackデータ構造を持っていて、その実現にImmutable Stackを用いてみた、といった形だ. 目指していたゴールとしては、

• Stackの更新時に一切Copyを発生させない.

だった. しかし今のところ下記のような理由でこれはうまくいっていない. (もしかしたらまだ思いついていない解決策があるかもしれない.)

• Stackの更新には、古いStackが必要. (例えば pop()の実装は fn pop(self) -> (Self, Option<T>) みたいな感じになっている)
• つまり、Stackの所有権を1度捨てる必要がある.
• しかしこれはUserの所有物であるStackを消費することになり、引き続きUserを使用する場合は新規でUserを作成してそれを返してあげる必要がある.

このようにImmutable Stackをある構造体の中に入れて管理しようとすると、Stackを更新する際に結局User自身を更新する必要が出てくる. これを許容するには、Stackを更新するUserのメソッドでも、self(User)を返してあげる必要がある.

ただそうすると、Userは一般にImmutableなデータ構造であるとは限らないので、結局Userのコピーが強いられることになりかねなくてetc...