How to get an infinitely nested value?

Question

In Rust, how can I get an infinitely nested value, such as the limit point of Peano numbers, or a list with infinitely many values?

In Haskell, such things are no big deal:

data Peano = Zero | Succ Peano

omega :: Peano
omega = fix Succ

But can such thing be done in Rust? I tried this:

enum Peano<'a> {
    Zero,
    Succ(&'a Peano<'a>)
}

fn main() {
    let omega = Peano::Succ(&omega);
}

And I cannot use omega during its initialization.

I also tried this:

enum Peano {
    Zero,
    Succ(fn () -> Peano)
}

fn main() {
    let omega = Peano::Succ(|| omega);
}

And the same problem persists.

Answer 1

Rust does not have built-in garbage collection, so by default you cannot naively create self-referential values except for static/leaked ones. Here's a static infinite structure (which is constructed at compile time, so the compiler can see the dependencies and know it's possible to assemble “timelessly”):

enum Peano<'a> {
    Zero,
    Succ(&'a Peano<'a>)
}

static OMEGA: Peano<'static> = Peano::Succ(&OMEGA);

Here's how to use a function to build a structure that is generated as you walk it — this is allowed because function items also exist statically/timelessly, so you can use a function inside itself (just like in a recursive function):

enum Peano {
    Zero,
    Succ(fn() -> Peano)
}

fn omega() -> Peano {
    Peano::Succ(omega)
}

If you want run-time construction of run-time chosen values, you'll need to use dyn functions that can be closures, and to let the function reference itself is a little tricky to set up:

use std::rc::{Rc, Weak};

enum Peano {
    Zero,
    Succ(Rc<dyn Fn() -> Peano>)
}

fn omega() -> Peano {
    let f = Rc::new_cyclic(|f: &Weak<_>| {
        // owned weak reference
        let f = f.clone() as Weak<dyn Fn() -> Peano>;
        move || Peano::Succ(f.upgrade().unwrap())
    });
    f()
}

The use of weak reference-counting here prevents omega() from being a memory leak, because strong references are only produced when the structure is traversed. (It would be a memory leak if you upgrade()d the Weak to Rc before constructing the closure instead of inside it.)

Note that these options involving functions are “lazy” but they are not memoizing. That would be possible but have additional work, and it would require adding a garbage collector library if you want to memoize a cyclic structure (as opposed to merely instantiating as many identical nodes of the infinite list as you traverse).

---

All this said, if you want to work with infinite lists in Rust, a much more idiomatic and flexible way to do that is to define them as iterators. An Iterator<()> will work as a Peano number, and omega is std::iter::repeat(()).