Demo of a viable beginner's process for constructing a simple functional program

I did a little experiment this evening, in incrementally designing a functional program, in reference to an earlier thread from today, and getting set off track, losing my way in compiler error messages on long chains of functions on iterators.

The following process worked quite well for me, in discovering where the type errors could potentially arise. I thought I would share my process, related to the question above. This will all seem very basic to some, which is probably a sign that it's a decent process.

In a nutshell the process is:

  1. Have some idea of a viable test for the function to be written.
  2. Write the function signature, enter a temporary placeholder for its return value
  3. In a series of immutable let statements, define the function. Try never to exceed more than two to three levels of indentation on each let.
  4. Test the function.
  5. Refactor the function to be done in fewer steps, as this is probably faster and easier to read besides
  6. optional Write a forum post about newfound enlightenment.

I have a predicate I'd like to write, called is_curious, where a curious number is one that satisfies the property:
the sum of the factorials of the digits equals the number. Eg, 1!+4!+5!=1+24+120=145.
That's a decent thought for step 0: Have some idea of a viable test for the function to be written.

  1. Write the function signature, enter a temporary placeholder for its return value
    I thus need to take the some integer x, and spit out a boolean.
    I throw true in as a placeholder return so the code will compile.
fn is_curious(x: u32) -> bool { 
  true
}

The hard part is done. Now to write the function.

  1. In a series of immutable let statements, define the function. Try never to exceed more than two to three levels of indentation on each let.

In the past, I've try to write the whole function in one go, and get stuck in the middle, and get side tracked.
Following the advice from earlier today, I'm going to write the function incrementally.
First, I want a str holding x, since str is easier to index than a u32.

fn is_curious(x: u32) -> bool { 
    let s: &str = &format!("{}", x);
  true
}

fiddle a little bit, Cargo run and bang, this compiles.
Next I'd like to toss that into a vector of one digit u32s that I can pass to a factorial function. I thought I wanted u8's originally but the <char>.to_digit() function returns u32, and I don't need to convert them.

fn is_curious(x: u32) -> bool { 
    let s: &str = &format!("{}", x);
    let v: Vec<u32> = s.chars().map(|c| c.to_digit(10).unwrap()).collect();

  true
}

Fiddles with unwrap and u32 instead of u8...compiles? Huzzah!
Finally I need to arrive at a sum of the factorials of each of the u32's I've just collected in a vector.

fn is_curious(x: u32) -> bool { 
    let s: &str = &format!("{}", x);
    let v: Vec<u32> = s.chars().map(|c| c.to_digit(10).unwrap()).collect();
    let sum = v.into_iter().fold(0, |acc, y| factorial(y) + acc);

  true
}

consider: iter and into_iter both work? yep. I suppose I don't need to reuse the things that came before, so into_iter is probably the better choice. Compiler buddy is mad I didn't write factorial :open_mouth:

factorial is a very simple function to write recursively:

fn factorial(x: u32) -> u32 {
    if x <= 1 {
        return 1; // TIL why this has to be a "return" not just 1, thx to alice
    }
    x * factorial(x - 1)
}

Shhh Gamma function nerds.
Compiler squeals in delight
And now we're ready to change the last bit of the is_curious function to something other than a placeholder.

fn is_curious(x: u32) -> bool {
    // using this slows runtime by roughly 2.3 times.
    let s: &str = &format!("{}", x);
    let v: Vec<u32> = s.chars().map(|c| c.to_digit(10).unwrap()).collect();
    let sum = v.into_iter().fold(0, |acc, y| factorial(y) + acc);
    if sum == x {
        return true;
    }
    false
}

two thumb twiddles for good luck, and the compiler doesn't say a word

  1. Test the function.

Set up that quick test in main:

fn main(){
  assert!(is_curious(145));
}

Cargo run -> ooh la la.
But we're not really done, because we can make this about 2.3 times as fast with a final refactoring of is_curious. (How I arrived at 2.3, scroll to bottom)

  1. Refactor the function to be done in fewer steps, as this is probably faster and easier to read besides

Turns out, is_curious could be a lot faster if we did all three steps in one step. I copy and paste a duplicate of the is_curious function, and relabel one of them is_curious_slow.

Could throw a #[allow(dead_code)] too, but I didn't.

Delete a few semicolons and lets between the lines, a collect there, and an into_iter* here, and we arrive at:

fn is_curious(x: u32) -> bool {
    // e34
    let sum: u32 = format!("{}", x)
        .chars()
        .map(|c| c.to_digit(10).unwrap())
        //.into_iter()
        .fold(0, |acc, y| factorial(y) + acc);
    if sum == x {
        return true;
    }
    false
}

*I actually didn't realize I could delete the into_iter until I wrote this post.
I stared at the if statement for a bit. I don't see a way to wrap it into the one step, so I left it.

This may have seemed pretty basic, but it was about as efficient as I've ever been writing in functional style. I've a few :clap: other :clap: posts where I struggled to do this, and this was useful for me as an exercise. Maybe it will help someone else.

  1. optional Write a forum post about newfound enlightenment.

I discovered this forum about a week ago. I've never felt so supported by an online community. That's pretty special. Thanks for that guys and gals and non-binary folks.

4 Likes

Since Rust is an expression language the last four lines can be reduced to
sum == x

1 Like

Note also that instead of an early return in the if, your factorial is typically written with an else block:

fn factorial(x: u32) -> u32 {
    if x <= 1 {
        1
    } else {
        x * factorial(x - 1)
    }
}

Now it doesn't need the return anymore. Note that your fold can also be written with sum():

let sum = v.into_iter().map(factorial).sum();
1 Like

Also, factorial can be written quite neatly like this:

fn factorial(n: u32) -> u32 {
    (2 ..= n).product()
}

This works for 0 and 1 because 2 ..= 0 is an empty iterator, and product() returns one for empty products.

Looks like the .map(factorial).sum() method's about 10% slower before optimizations. I'm also surprised that you can call map like that. Nifty.

:eyes: Have you considered benchmarking with optimizations?

Looks like using
A. my original factorial and my original is_curious takes 300ms
B. the new factorial and my original is_curious takes 290ms
C. the new factorial and the new is_curious takes 300ms
after building with the release flag. I don't know how to benchmark yet

You should consider looking into criterion for benchmarking as it uses better statistical tools than you probably are.

1 Like

Being blocked by unstable errors. Was following this, is bench only on unstable rust? Is there a quick way to tell my compiler it's okay to go out into unstable world?

That link is from Rust 1.2 in 2015; I suggest following this instead, to use the library @alice recommended: https://bheisler.github.io/criterion.rs/book/index.html

Instead of converting to a string and looking at characters, you can get the digits through the modulo operator on the u32

I’ll try to follow up with something more specific when I get to a real keyboard.

PS: As a Gamma function nerd, I approve of your approach for factorials of single digit numbers.

1 Like

My immediate thought was that since you are only ever going to take the factorial of 10 different numbers (the digits) it might be quicker to create an array size 10 with the factorials in it and declare this (as a constant) somewhere and lookup the digits and sum the entries. Thus saving the calculation of factorial each time.

This would work whether you had a string (and indexed with characters) or a number (and indexed with integers (found mod 10).

It might even become a one-line functional program being the sum of the map of the digits into the array.