The need for an enumeration where few values have a name and are special, and all the other values are just numeric values is very common, I have encountered it already few times in my Rust coding (and I think Ada language enums allow you to handle it).
This is a case I've found few days ago, this is a solution for the Euler Problem 14 (#14 Longest Collatz sequence - Project Euler ):
fn collatz_chain_len_direct(n: usize, cache: &mut [Option<u32>]) -> u32 {
match n {
1 => 1,
n if n % 2 == 0 => collatz_chain_len(n / 2, cache) + 1,
_ => collatz_chain_len(3 * n + 1, cache) + 1
}
}
fn collatz_chain_len(n: usize, cache: &mut [Option<u32>]) -> u32 {
match cache.get(n) {
None => collatz_chain_len_direct(n, cache), // Caching not available.
Some(&None) => { // Missing in cache.
let len = collatz_chain_len_direct(n, cache);
cache[n] = Some(len);
len
},
Some(&Some(len)) => len
}
}
fn main() {
const LIMIT: usize = 1_000_000;
const CACHE_SIZE: usize = LIMIT;
let mut cache = vec![None; CACHE_SIZE];
let max_index = (1 .. LIMIT)
.max_by_key(|&i| collatz_chain_len(i, &mut cache));
println!("{:?}", max_index);
}
"cache" is a vector of Option, and it's used for memoization, to avoid many re-computations, where "None" represents a not yet computed value.
If you replace the Option with a u32, in this case you can use 0 to represent None (because the chain lengths are always >= 1):
const NONE: u32 = 0;
fn collatz_chain_len_direct(n: usize, cache: &mut [u32]) -> u32 {
match n {
1 => 1,
n if n % 2 == 0 => collatz_chain_len(n / 2, cache) + 1,
_ => collatz_chain_len(3 * n + 1, cache) + 1
}
}
fn collatz_chain_len(n: usize, cache: &mut [u32]) -> u32 {
match cache.get(n) {
None => collatz_chain_len_direct(n, cache), // Caching not available.
Some(&NONE) => { // Missing in cache.
let len = collatz_chain_len_direct(n, cache);
debug_assert!(len != NONE);
cache[n] = len;
len
},
Some(&len) => len
}
}
fn main() {
const LIMIT: usize = 1_000_000;
const CACHE_SIZE: usize = LIMIT;
let mut cache = vec![NONE; CACHE_SIZE];
let max_index = (1 .. LIMIT)
.max_by_key(|&i| collatz_chain_len(i, &mut cache))
.unwrap();
println!("{}", max_index);
}
This version of the program is faster, you can see it even better if you set LIMIT=10Millions (perhaps because cache uses half the memory, and this improves CPU cache coherence), but it's less elegant, and probably less safe too (in this program I have added a debug_assert, but in other similar programs if you forget to add it, you may sometimes write the NONE value by mistake).
In a well designed system language I'd like to keep the cake and eat it too, as they say. This means having a way to represent Option with just 32 bits, with a special value chosen by me, keep the whole code simpler, safer with appropriate debug_asserts added by the compiler where you insert something in the variables, with no need for global constants like NONE, and so on, and have the faster code.
Rust being a system language, the desire to manually manage enums and tags comes out often. There are vague proposals to user-manage manually tags and contents, to solve your problem. This topic was discussed recently for the "union structs" RFC, but I don't remember the ergonomy of those proposals.
