Hello,
Is it possible to define an infinite array? For example, let mut x = [0;];.
Thank you.
No.
Does your computer have infinite address space and infinite memory? That would be a neat trick.
5 Likes
An array has to store each element, so no.
You may be interested in an iterator that produces as many zeros as you want std::iter::repeat(0).
2 Likes
Is there any programming language where you can define infinite arrays that are proper arrays? In the sense of being backed by a continuous slice of memory.
In haskell you can create an infinite linked list using the fact that haskell is a lazy language where things are only computed once you need them. So the linked list value would initially be a thunk, then when you force evaluating of it, it would return a value for the head and another thunk for the tail. It also replaces the thunk itself with the new value to avoid repeated evaluation. This of course doesn't give you a contiguous slice of memory representing the infinite linked list, but from the perspective of the programmer it looks like the entire infinite list exists at once assuming that the computation of the linked list doesn't go into an infinite loop without producing new list elements.
1 Like
Rust has no support for lazy datastructures in stdlib, no.
If you want them, you'll either have to find them on crates.io, or write them yourself.
Hello,
Thank you so much for your reply.
Why vector can? For example, let mut x = vec![];.
Depending on what you need it for, iterators provide some of the functionality of infinite lazy lists, but they can only be iterated once. For example, you can implement an iterator over the fibonacci numbers in functional way:
fn main() {
let fib = std::iter::successors(Some((0, 1)), |(a,b)| Some((*b, a+b))).map(|(a,b)| a);
dbg!(fib.take(40).collect::<Vec<_>>());
}
1 Like
vec![] is a vector that can grow, but is initially empty. If you insert too many elements you'll get an out-of-memory error.
3 Likes
When your elements consume 0 bytes memory (zero-sized types), then it's possible to have very large arrays:
use std::fmt;
#[derive(Copy, Clone, Debug)]
struct Foo;
impl fmt::Display for Foo {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
write!(f, "I'm a foo!")
}
}
fn main() {
let very_large = [Foo; usize::MAX];
println!("{}", very_large[18446744073709551614]);
//println!("{}", very_large[18446744073709551615]); // would panic on 64 bit platform
}
Output:
I'm a foo!
Generally, arrays will always be as big as each element [1] times the number of elements in the array. An array with a non-zero byte element that is infinite elements long would consume an infinite amount of memory. That's not possible.
But arrays are really much more seldom used than Vecs. Why is that? Because Vec's can grow as needed, but references both to Vecs as well as to arrays will coerce into slices:
fn foo(slice: &[i32]) {
println!("Got: {:?}", slice);
}
fn main() {
let mut array = [4, 2, 55];
array[2] += 1;
//array.push(99); // doesn't work
let mut vec = Vec::with_capacity(0);
vec.push(15);
vec.push(17);
vec[1] += 1;
foo(&array); // this works
foo(&vec); // this works too!
}
Output:
Got: [4, 2, 56]
Got: [15, 18]
Note that the capacity (not to be confused with the length of a Vec) is just a hint for optimization. It can be exceeded, like in the example above where the capacity is 0, originally, but the Vec can grow beyond that.
So what does that mean for practical programming:
- If you want to change the length of a list, use
Vec(optionally with a capacity set to the number of elements you expect). - If you know the length you may use an array. Note, however, that this may be bad for long arrays as they don't always end up on the heap memory (if I understand right).
- When passing
Vecs or arrays to functions, which do not need to change the length, then use references to slices (&[T]or&mut [T]).
-
including alignment padding ↩︎
3 Likes
AFAIK, Arrays are in general on the stack, but you can have boxed arrays on the heap.
Well, not only in case of Boxes. For example, if you have them in a Vec, they will be on the heap too.
1 Like
You didn't state your exact problem you need this for, but a HashMap<usize, T> might emulate what you need closely enough. You could build a wrapper that behaves like an infinitely-sized [Option<T>;]. (If you don't want Option here then you could build something without if T: Default)
2 Likes
Nice idea:
use std::collections::HashMap;
use std::ops::{Index, IndexMut};
pub struct InfAry<T> {
empty: T,
inner: HashMap<usize, T>,
}
impl<T: Default> InfAry<T> {
pub fn new() -> Self {
Self {
empty: Default::default(),
inner: HashMap::new(),
}
}
pub fn remove(&mut self, index: usize) -> Option<T> {
self.inner.remove(&index)
}
}
impl<T: Default> Index<usize> for InfAry<T> {
type Output = T;
fn index(&self, index: usize) -> &T {
self.inner.get(&index).unwrap_or(&self.empty)
}
}
impl<T: Default> IndexMut<usize> for InfAry<T> {
fn index_mut(&mut self, index: usize) -> &mut T {
if !self.inner.contains_key(&index) {
self.inner.insert(index, Default::default());
}
self.inner.get_mut(&index).unwrap()
}
}
fn main() {
let mut inf_ary = InfAry::<String>::new();
inf_ary[2147483600] = "Hello!".to_string();
inf_ary[2000000003] = "How are you?".to_string();
println!("{}", &inf_ary[2147483600]);
println!("{}", &inf_ary[2000000003]);
assert_eq!(&inf_ary[1234], "");
}
Output:
Hello!
How are you?
P.S.: Note that this isn't really an "array" even if I named it Ary: It's not possible to obtain a slice of contiguous items, for example.
1 Like
Rust has iterators such as 0…. It is lazy. Under the hood, like Haskell, the Iterator is a generator. Haskell’s default is lazy, not so in Rust. Whenever you have to call collect() you’re dealing with a lazy expression in Rust (there are others, eg take If memory serves).
A generator in mathematical terms can create a set of values (e.g., all values for a given type) using a seed value, and the values it subsequently creates. E.g., lambda Zero: Nat and Succ: Nat -> Nat can be used to generate the infinite [1] set of positive whole numbers (Nats)… evaluated “on demand” per the take(how_many) method.
Finally, it’s this lazy quality of iterators in Rust that can often have map and friends execute faster than a for loop. The lazy quality gives the compiler a chance to optimize the composed iterators prior to the call to collect. So, best to delay that call to collectas long as possible.
or to whatever u8, u16, u32 etc can host ↩︎
A Generator in (unstable) Rust is something else. Iterators are implemented via this vanilla trait, not coroutines.
Maybe this is a just a terminology mismatch with Haskell.
2 Likes
Thank you for pointing out my potentially confusing use of the term. I’m not familiar with the soon to be generator feature, but if it’s anything like that in JS, I’m not using the term that way.
The concept I’m describing is what makes it possible to express infinitely sized sets in CS. In set theory, if a set is not made up of random elements, there is some sort of “structure” (pattern). If you can express the structure in a function, you have a “generator”. It’s the opposite of a “fold” that reduces a set of elements to a single value.
Well, you could emulate that too if you wanted to. You'd need to build a borrowed version of your InfAry which could then be returned by range slicings.