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.

I'd specifically look into the `Rc`/`Arc` options mentioned by the most upvoted answer, they have a `new_cyclic` constructor which might be what you want. — cafce25, Apr 09 '23 at 04:27
I'm not sure that the given duplicate is the best choice. If you read between the lines of what OP is _really_ want to do, they are looking for a way to emulate lazy evaluation, and build a lazily evaluated recursive type, which would allow the construction infinite values, not just arbitrarily large values. — Peter Hall, Apr 09 '23 at 09:28
Browsing the [tag:fixpoint-combinators], I have l notice [someone who came up with a version in JS](https://stackoverflow.com/q/68975627/157957). I wonder if that could provide any suitable inspiration? — IMSoP, Apr 09 '23 at 09:49
To start with, you need to have some concept of lazy evaluation. I'm sure you can do this (in a very verbose and ugly way) in Rust. — Peter Hall, Apr 09 '23 at 10:28
I think what you are trying to achieve here isn't really suitable to the Rust language. Usually things like infinite lists are achieved through infinitely generating iterators. Be aware that Rust isn't fully functional; in its base paradigm, it is a procedural language with functional elements. — Finomnis, Apr 09 '23 at 13:37

Kevin Reid · Accepted Answer · 2023-04-10T01:34:20.663

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(()).

How to get an infinitely nested value?

1 Answers1