I'm now writing many small Rust programs, some of them are Project Euler solutions and similar things, and some of them are practical (sometimes they are Rust translations of small programs I wrote in Python, D and Haskell).
Writing so many small programs I'm seeing that the Rust standard library lacks some small functions/features (and most of them are already present in some external crates!) that I think are basic and useful in many different situations.
I don't yet know what rules Rust follows to decide to keep something in external crates, or to add it to the standard library. So do you know what those rules are?
But I am not asking for std library features yet. In this post I prefer to talk about something more general.
This is the Euler Project Problem 61:
This is a very nice solution in Haskell (the original code is not mine. But I've tried to improve this code in some ways):
import Data.List (permutations)
poly :: Int -> [Int]
poly x = takeWhile (< 10000) $ dropWhile (< 1000) $ scanl (+) 0 [1, x - 1 ..]
isRow :: Int -> Int -> Bool
isRow a b = mod a 100 == div b 100
solve :: [Int] -> [Int]
solve [x3, x4, x5, x6, x7, x8] =
[sum [a, b, c, d, e, g] | a <- poly x3,
b <- filter (isRow a) $ poly x4,
c <- filter (isRow b) $ poly x5,
d <- filter (isRow c) $ poly x6,
e <- filter (isRow d) $ poly x7,
g <- filter (isRow e) $ poly x8,
isRow g a]
e61 = head $ concatMap solve $ map (8:) $ permutations [3 .. 7]
main = print e61 -- 28684
I have tried to translate it to Rust:
#![feature(iter_arith)]
fn concat<T: Clone>(v1: &[T], v2: &[T]) -> Vec<T> {
let mut v1c = v1.to_vec();
v1c.extend_from_slice(v2);
v1c
}
fn permutations<T: Clone + Copy>(items: &[T]) -> Vec<Vec<T>> {
fn perms<T: Clone + Copy>(s: &[T], prefix: Vec<T>, result: &mut Vec<Vec<T>>) {
if s.is_empty() {
result.push(prefix);
} else {
for (i, &c) in s.iter().enumerate() {
perms(&concat(&s[..i], &s[i + 1..]), concat(&prefix, &[c]), result);
}
}
}
let mut result = vec![];
perms(items, vec![], &mut result);
result
}
fn poly(x: usize) -> Vec<u32> {
let mut result = vec![];
let mut n = 0;
for i in 0 .. {
n += i * (x - 2) + 1;
if n < 1_000 { continue; }
if n >= 10_000 { break; }
result.push(n as u32);
}
result
}
fn is_row(a: u32, b: u32) -> bool { a % 100 == b / 100 }
fn solve(xs: &[usize], polys: &[Vec<u32>]) -> Vec<u32> {
let (x3, x4, x5, x6, x7, x8) = (xs[0], xs[1], xs[2], xs[3], xs[4], xs[5]);
polys[x3 - 3].iter().flat_map(|&a|
polys[x4 - 3].iter().filter(move |&&b| is_row(a, b)).flat_map(move |&b|
polys[x5 - 3].iter().filter(move |&&c| is_row(b, c)).flat_map(move |&c|
polys[x6 - 3].iter().filter(move |&&d| is_row(c, d)).flat_map(move |&d|
polys[x7 - 3].iter().filter(move |&&e| is_row(d, e)).flat_map(move |&e|
polys[x8 - 3].iter().filter(move |&&g| is_row(e, g))
.filter(move |&&g| is_row(g, a))
.map(move |&g| [a, b, c, d, e, g].iter().sum()))))))
.collect::<Vec<_>>()
}
fn main() {
let polys = (3 .. 9).map(poly).collect::<Vec<_>>();
let e61 = permutations(&[3, 4, 5, 6, 7])
.iter()
.flat_map(|p| solve(&concat(&[8], &p[..]), &polys))
.next()
.unwrap();
println!("{}", e61); // 28_684
}
This Rust code compiles, runs very quickly, and gives the right answer (and in my opinion it shows some things that should be present in the Rust standard library, but I leave this to other posts), and if you have suggestions to improve the code they are welcome.
But on my fast enough computer it compiles without optimizations in about 12.4 seconds. I think that's a bit too much for a 53 cloc lines long program
I am aware that rewriting the program in a C-style way, the Rustc compiler is probably able to compile it on my pic in 1.5 seconds. All those iterators slow the compilation down a lot, I guess. If you use such iterator-heavy code for thousands of lines I think the compilation times become excessive, even on the fastest PCs.