FizzBuzz Can Finally Be Implemented in Stable Rust
I have been editing my FizzBuzz repository since 2014. After four years, I was finally able to switch from nightly to stable due to the 1.26 release. Let’s back up a little bit and appreciate the changes since the first revision.
trait Monoid {
// don't have assoc. values yet, so us a nullary function
fn id() -> Self;
// an associative binary operation
// this version consumes arguments
// a non-consuming version might be possible
fn op(self, other: Self) -> Self;
}
// owned strings implement append
impl Monoid for ~str {
fn id() -> ~str { ~"" } // identity is empty string
fn op(self, other: ~str) -> ~str {
self.append(other)
}
}
// not sure if we can impl Monoid for &str
// Options are Monoids if they contain Monoids
impl<A: Monoid> Monoid for Option<A> {
fn id() -> Option<A> { None }
fn op(self, other: Option<A>) -> Option<A> {
match (self, other) {
(None, b) => b,
(a, None) => a,
(Some(a), Some(b)) => Some(a.op(b)),
}
}
}
fn fizzbuzz(i: int) -> ~str {
// filtered is the equivalent a comprehension guard
// unwrap_or is fromMaybe
Some(~"fizz").filtered(|_| i % 3 == 0).op(
Some(~"buzz").filtered(|_| i % 5 == 0)
// we can add more conditions by appending
// a .op( above and inserting a new line below
).unwrap_or(i.to_str())
}
fn main() {
let args = std::os::args();
match from_str::<int>(args[1]){
Some(x)=>for i in std::iter::range_inclusive(1, x) {
println!("{}", fizzbuzz(i));
},
None=>println!("I need a real number")
}
}This was the first version and it wasn’t actually written by me. I asked how to port https://web.archive.org/web/20130511210903/http://dave.fayr.am/posts/2012-10-4-finding-fizzbuzz.html to Rust and someone from IRC helped me.
Historical note: look at the ~ pointers, std::iter::range_inclusive, int type, etc.
This version is nice in that to add a condition like “if it’s divisible by 7, write Bazz” is fairly simple. But we can definitely do better. Instead of having to change the program, we can actually just have our FizzBuzz function take an array of strings and divisors. Meanwhile, I had to upgrade to Rust 0.11 and switch from ~str to the String type.
fn fizzbuzz(i: int) -> String {
// filtered is the equivalent a comprehension guard
// unwrap_or is fromMaybe
fizzbuzz_op(i, None,
[("Fizz".to_string(), 3), ("Buzz".to_string(), 5), ("Bazz".to_string(), 7)]
).unwrap_or(i.to_str())
}
fn fizzbuzz_op(i: int, res: Option<String>, rest: &[(String, int)]) -> Option<String> {
match rest {
[ref first, .. tail] => fizzbuzz_op(
i,
res.op(Some(first.ref0().clone()).filtered(|_| i % *first.ref1() == 0)),
tail
),
_ => res
}
}This still isn’t quite as general. Why is the condition always “divisible by” and not something else?
pub fn op_filter(tuples: &[(&'static str, &Fn() -> bool)]) -> Option<String> {
tuples.iter().fold(None, |res, &(value, include)|
res.op(utils::filter(Some(value.to_string()), include()))
)
}That’s getting pretty abstract, but the point is still the same: we’re testing an integer for all of the conditions for inclusion of a String. If a String is not included, we just return None. The problem with this function is that it conflates the fold operation with the filtering. But before we fixed that, range_inclusive got removed so now we either have to write a while loop and manually iterate, or we have an overflow bug when the user gives us the maximum int. This is the first blocker to FizzBuzz on stable. It’s just ugly to do a while loop or have an overflow!
A user on /r/rust suggested we do this
for i in 1..n.checked_add(1).expect("Integer overflow") { ... }But this handles one less value than the correct inclusive range, as well as being ugly. The other blocker appeared when I started writing my filter function.
//does the monoid operation on the slice of tuples if the closure evaluates to true
fn accumulate<'a, T: Monoid>(tuples: &[(&'a str, &Fn(i32) -> bool)], i: i32) -> Option<T>
where &'a str: Into<T> {
tuples.iter()
.filter(|&x|second(x)(i)) //don't try to make this point-free it's point-less
.map(first)
.cloned()
.map(<&str>::into)
.fold1(T::op)
//op just concatenates, but Cow<'a, str> does not satisfy Add
}We’re using fold1 from itertools here. It folds starting from None and folds Option<Monoid> using Monoid::op (which in our case is concatenation).
Despite that comment, I still wanted to make that inside part of the filter point-free because I don’t like how it’s harder to read with more sigils.
//does the monoid operation on the slice of tuples if the closure evaluates to true
fn accumulate<'a, T: Monoid>(tuples: &[(&'a str, &Fn(i32) -> bool)], i: i32) -> T
where T: From<&'a str> + From<String> {
tuples.iter()
.filter(apply(second, i))
.map(first)
.cloned()
.map(<&str>::into)
.fold1(T::op)
.unwrap_or_else(|| i.to_string().into())
//op just concatenates, but String does not satisfy Add
}
fn apply<A, B, C, F, G>(mut f: F, a: A)
-> impl FnMut(&B) -> C // must still be `for<'r> impl FnMut(&'r B) -> C`, because that’s what filter requires
where F: FnMut(B) -> G, // must not be `for<'r> FnMut(&'r B) -> G`, because regular functions do not implement it
G: FnMut(A) -> C,
B: Copy, // for dereferencing
A: Clone {
move |b| f(*b)(a.clone()) // this must do any bridging necessary to satisfy the requirements
}There’s our second blocker. To make a function that applies an argument and returns a closure taking another argument I had to use existential types. Another 1.26 feature! Of course, the apply function is more complicated than our closure, but I was envisioning putting this in some kind of a library. Unfortunately, this cannot be done now because the current apply is extremely limited to my exact case. See:
A more general version is probably possible when Rust has better higher-kinded polymorphism. But with the release of 1.26 I can compile this function on stable because it supports -> impl Fn. With the release of inclusive ranges I can do something like this as well:
let acc = (1..=15).map(|i| fizzbuzz::fizzbuzz(&[
("Fizz", &|i: i32| i % 3 == 0),
("Buzz", &|i: i32| i % 5 == 0),
], i)).collect::<Vec<_>>().join(" ");
assert_eq!(acc, "1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz".to_string());Throughout the years, I was learning Rust and keeping up with its progress by modifying this repository. I wrote tests, benchmarks (Cow<’a, str>is faster than String!), documentation, a Monoid dependency, etc. I bumped up against limitations of functional programming in Rust that made it not possible to generalize the apply function. I’m very excited about being able to compile it on stable Rust without having to modify my code to look more ugly. I’m looking forward to further improvements to Rust that would allow me to take out dereferencing out of my apply function and to be able to stick apply into some outside library for everyone’s use.
The final result is here https://bitbucket.org/iopq/fizzbuzz-in-rust/src/
Addendum: I have since updated my Monoid crate to use a const ID instead of a function. Version 0.0.6 now requires the nightly Rust version because of String::new() not being const on stable.