SICP-RS: Exercise 1.3 - Sum of Squares
Part 1 of the SICP-RS Series
The first coding exercise we come to in Chapter 1 of Structure and Interpretation of Computer Programs is Exercise 1.3:
Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers. [1]
Step 1: square Procedure
The first thing we need to do is square a number. In the book, there is a procedure square that squares a given number:
(define (square x) (* x x))
It is a procedure that takes one argument, and returns that argument squared by itself.
So how would we go about doing the same in Rust? Here is one approach, along with a test to make sure it all worked:
use std::ops::Mul;
/// Square of a given number
fn square<T>(x: T) -> T
where
T: Copy + Mul<Output = T>,
{
x * x
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_square() {
assert_eq!(square(2), 4);
}
}
This could be simpler if we require the developer to pass a certain type of number, like i32 or f64. But the Scheme version doesn't make similar assumptions. The square procedure could take any kind of number in Scheme!
So I used Rust Generics and Trait Bounds to allow our square function to be able to take any argument of type T that satisfies the given traits, specifically Copy and Mul which allows us to multiply the argument by itself.
We can already tell that our Rust implementations are not going to be as concise as the Scheme ones :)
Step 2: sum_of_squares Procedure
The next thing we need is a procedure that returns to sum of the squares of two numbers. Thankfully, the book also provided an implemenation to show how procedures can call other procedures.
(define (sum-of-squares x y)
(+ (square x) (square y)))
We take two arguments, x and y, pass both of them to the square procedure we defined earlier, and add them together. Pretty straightforward.
The Rust version looks very similar, albeit with some more trait bounds thrown in:
use std::ops::{Add, Mul};
/// Sum of squares of two inputs
fn sum_of_squares<T>(x: T, y: T) -> T
where
T: Copy + Add<Output = T> + Mul<Output = T>,
{
square(x) + square(y)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sum_of_squares() {
assert_eq!(sum_of_squares(1, 2), 5);
assert_eq!(sum_of_squares(2, 3), 13);
}
}
Just like in Scheme, we can leverage the function we already created for our square logic, and add the output together after passing both x and y in to it.
The trait bounds look very similar, but we add to add a new one: Add. For this function, not only must T implement the ability to multiply, we now also need it to be added together.
sum_of_largest_two_squares Procedure
With the two previous procedures, we have almost everything we need to solve the exercise. We can square a number and return the sum of the squares of two numbers. Now we need to be able to take three numbers and return the sum of the squares of the largest two numbers.
An implementation in Scheme could look like this:
(define (sum-of-largest-squares x y z)
(cond
((and (>= x z) (>= y z))
(sum-of-squares x y))
((and (>= y x) (>= z x))
(sum-of-squares y z))
((and (>= x y) (>= z y))
(sum-of-squares x z))))
We are now using logical operators to make decisions in our procedure. cond lets us do a series of if checks, returning the result of whichever returns true first. We do several comparisons to find the largest two numbers, and then just pass them into sum-of-squares.
For the Rust version, we could probably leverage functions in the standard library or external crates to do a lot of this work for us. But in the spirit of doing it ourselves:
use std::cmp::Ord;
use std::ops::{Add, Mul};
pub fn sum_of_largest_two_squares<T>(x: T, y: T, z: T) -> T
where
T: Copy + Ord + Add<Output = T> + Mul<Output = T>,
{
if x >= z && y >= z {
sum_of_squares(x, y)
} else if y >= x && z >= x {
sum_of_squares(y, z)
} else {
sum_of_squares(x, z)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sum_of_largest_two_squares() {
let sum = sum_of_largest_two_squares(1, 2, 3);
assert_eq!(sum, 13);
let sum = sum_of_largest_two_squares(1, 1, 1);
assert_eq!(sum, 2);
let sum = sum_of_largest_two_squares(1, 2, 2);
assert_eq!(sum, 8);
let sum = sum_of_largest_two_squares(1, 1, 2);
assert_eq!(sum, 5);
}
}
Rust doesn't have a direct equivalent to cond, but it does have if/else blocks which work the same way. We also had to add one more trait bount to T: Ord. This is because we are now comparing this type, and so the type needs to implement a way to compare itself.
Conclusion
Other than some trait magic to allow our Rust functions to handle multiple number types[2], the Rust implementations were almost identical to the Scheme implementations. There are certainly some syntactical differences between the two languages, but the core logic was remarkably similar. We'll see how well that holds true for future exercises!
The full Rust implementation is below if you would like to see it all together. You can also view it on my github repository, along with the Scheme code as well.
use std::cmp::Ord;
use std::ops::{Add, Mul};
/// Square of a given number
fn square<T>(x: T) -> T
where
T: Copy + Mul<Output = T>,
{
x * x
}
/// Sum of squares of two inputs
fn sum_of_squares<T>(x: T, y: T) -> T
where
T: Copy + Add<Output = T> + Mul<Output = T>,
{
square(x) + square(y)
}
pub fn sum_of_largest_two_squares<T>(x: T, y: T, z: T) -> T
where
T: Copy + Ord + Add<Output = T> + Mul<Output = T>,
{
if x >= z && y >= z {
sum_of_squares(x, y)
} else if y >= x && z >= x {
sum_of_squares(y, z)
} else {
sum_of_squares(x, z)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_square() {
assert_eq!(square(2), 4);
}
#[test]
fn test_sum_of_squares() {
assert_eq!(sum_of_squares(1, 2), 5);
assert_eq!(sum_of_squares(2, 3), 13);
}
#[test]
fn test_sum_of_largest_two_squares() {
let sum = sum_of_largest_two_squares(1, 2, 3);
assert_eq!(sum, 13);
let sum = sum_of_largest_two_squares(1, 1, 1);
assert_eq!(sum, 2);
let sum = sum_of_largest_two_squares(1, 2, 2);
assert_eq!(sum, 8);
let sum = sum_of_largest_two_squares(1, 1, 2);
assert_eq!(sum, 5);
}
}
Thanks to the scheme community wiki for some great test case examples. Ensuring my rust implementation worked correctly was much easier with a standard test set.
