Learning from Multiple Solution Approaches
Welcome to the second article in our Rust vs. Haskell problem solving series. Last week we saw some basic differences between Rust loops and Haskell recursion. We also saw how to use the concept of “folding” to simplify a recursive loop function.
This week, we’ll look at another simple problem and consider multiple solutions in each language. We’ll consider what a “basic” solution looks like, using relatively few library functions. Then we’ll consider more “advanced” solutions that make use of library functionality, and greatly simplify the structure of our solutions.
To learn more about problem solving in Haskell, including the importance of list library functions, take a look at our course Solve.hs! You’ll write most of Haskell’s list API from scratch so you get an in-depth understanding of the functions that are available!
The Problem
This week’s problem is Reverse Words in a String. The idea is simple. Our input is a string, which naturally has “words” separated by whitespace. We want to return a string that has all the words reversed! So if the input is ”A quick brown fox”, the result should be ”fox brown quick A”.
Notice that all whitespace is truncated in our output. We should only have a single space between words in our answer, with no leading or trailing whitespace.
The Algorithm
The algorithmic idea is simple and hardly needs explanation. We want to gather letters from the input word until we encounter whitespace. Then we append this buffered word to a growing result string, and keep following this process until we run out of input.
There is one wrinkle, which is whether we want to accumulate our answer in the forward or reverse direction. This changes across languages!
In Haskell, it’s actually more efficient to accumulate the “back” of our resulting string first, meaning we should start by iterating from the front of the input. This is more consistent with linked list construction.
In Rust, we’ll iterate from the back of the input so that we can accumulate our result from the “front”.
Basic Rust Solution
In our basic solution, we’re going to consider a character-by-character approach. As outlined in our algorithm, we can accomplish this task with a single loop, with two stateful values. First, we have the “current” word we’re accumulating of non-whitespace characters. Second, we have the final “result” we’re accumulating.
It’s efficient to append to the end of strings, meaning we want to construct our result from front-to-back. This means we’ll loop through the characters of our string in reverse, as shown with .rev() here:
pub fn reverse_words(s: String) -> String {
let mut current = String::new();
let mut result = String::new();
for c in s.chars().rev() {
...
}
}Within the loop, we now just have to consider what to do with each character. If the character is not whitespace, the answer is simple. We just append this character to our “current” word. Because we’re looping through the input in reverse, our “current” word will also be in reverse!
pub fn reverse_words(s: String) -> String {
let mut current = String::new();
let mut result = String::new();
for c in s.chars().rev() {
if !c.is_whitespace() {
current.push(c);
} else {
...
}
}
}So what happens when we encounter whitespace? There’s a few conditions to consider:
- If “current” is empty, do nothing.
- If “result” is empty, append “current” (in reverse order) to result.
- If “result” is not empty, add a space and then append “current” in reverse.
- Regardless, clear “current” and prepare to gather a new string.
Here’s what the code looks like:
pub fn reverse_words(s: String) -> String {
let mut current = String::new();
let mut result = String::new();
for c in s.chars().rev() {
if !c.is_whitespace() {
current.push(c);
} else {
// Step 1: Skip if empty
if !current.is_empty() {
// Step 2/3 Only push an empty space is result is not empty
if !result.is_empty() {
result.push(' ');
}
// Step 2/3 Reverse current and append
for b in current.chars().rev() {
result.push(b);
}
// Step 4: Clear “current”
current.clear();
}
}
}
}There’s one final trick. Unless the word begins with whitespace, we’ll still have non-empty current at the end and we will not have appended it. So we do one final check, and once again append “current” in reverse order.
Here’s our final basic solution:
pub fn reverse_words(s: String) -> String {
let mut current = String::new();
let mut result = String::new();
for c in s.chars().rev() {
if !c.is_whitespace() {
current.push(c);
} else {
// Step 1: Skip if empty
if !current.is_empty() {
// Step 2/3 Only push an empty space is result is not empty
if !result.is_empty() {
result.push(' ');
}
// Step 2/3 Reverse current and append
for b in current.chars().rev() {
result.push(b);
}
// Step 4: Clear “current”
current.clear();
}
}
}
if !current.is_empty() {
if !result.is_empty() {
result.push(' ');
}
for b in current.chars().rev() {
result.push(b);
}
}
return result;
}Advanced Rust Solution
Looping character-by-character is a bit cumbersome. However, since basic whitespace related operations are so common, there are some useful library functions for dealing with them.
Rust also prioritizes the ability to chain iterative operations together. This gives us the following one-line solution!
pub fn reverse_words(s: String) -> String {
s.split_whitespace().rev().collect::<Vec<&str>>().join(" ")
}It has four stages:
- Split the input based on whitespace.
- Reverse the split-up words.
- Collect these words as a vector of strings.
- Join them together with one space in between them.
What is interesting about this structure is that each stage of the process has a separate type. Step 1 creates a SplitWhitespace struct. Step 2 creates a Reverse struct. Step 3 then creates a normal vector, and step 4 concludes by producing a string.
The two preliminary structures are essentially wrappers with iterators to help chain the operations together. As we’ll see, the comparable Haskell solution only uses basic lists, and this is a noteworthy difference between the languages.
Basic Haskell Solution
Our “basic” Haskell solution will follow the same outline as the basic Rust solution, but we’ll work in the opposite direction! We’ll loop through the input in forward order, and accumulate our output in reverse order.
Before we even get started though, we can make an observation from our basic Rust solution that we duplicated some code! The concept of combining the “current” word and the “result” had several edge cases to handle, so let’s write a combine function to handle these.
-- “current” is reversed and then goes in *front* of result
-- (Rust version put “current” at the back)
combine :: (String, String) -> String
combine (current, res) = if null current then res
else reverse current <> if null res then "" else (' ' : res)Now let’s think about our loop structure. We are going through the input, character-by-character. This means we should be able to use a fold, like we did last week! Whenever we’re using a fold, we want to think about the “state” we’re passing through each iteration. In our case, the state is the “current” word and the “result” string. This means our folding function should look like this:
loop :: (String, String) -> Char -> (String, String)
loop (current, result) c = ...Now we just have to distinguish between the “whitespace” case and the non-whitespace case. If we encounter a space, we just combine the current word with the accumulated result. If we encounter a normal character, we append this to our current word (again, accumulating “current” in reverse).
loop :: (String, String) -> Char -> (String, String)
loop (currentWord, result) c = if isSpace c
then ("", combine (currentWord, result))
else (c : currentWord, result)Now to complete the solution, we just call ‘foldl’ with our ‘loop’ and the input, and we just have to remember to combine the final “current” word with the output! Here’s our complete “basic” solution.
reverseWords :: String -> String
reverseWords input = combine $ foldl loop ("", "") input
where
combine :: (String, String) -> String
combine (current, res) = if null current then res
else reverse current <> if null res then "" else (' ' : res)
loop :: (String, String) -> Char -> (String, String)
loop (currentWord, result) c = if isSpace c
then ("", combine (currentWord, result))
else (c : currentWord, result)Advanced Haskell Solutions
Now that we’ve seen a basic, character-by-character solution in Haskell, we can also consider more advanced solutions that incorporate library functions. The first improvement we can make is to lean on list functions like break and dropWhile.
Using break splits off the first part of a list that does not satisfy a predicate. We’ll use this to gather non-space characters. Then dropWhile allows us to drop the first series of characters in a list that satisfy a predicate. We’ll use this to get rid of whitespace as we move along!
So we’ll define this solution using a basic recursive loop rather than a fold, because each iteration will consume a variable number of characters. The “state” of this loop will be two strings: the remaining part of the input, and the accumulated result.
Since there’s no “current” word, our base case is easy. If the remaining input is empty, we return the accumulated result.
loop :: (String, String) -> String
loop ([], output) = output
...Otherwise, we’ll follow this process:
- Separate the first “word” using
break isSpace. - Combine this word with the output (if it’s not null)
- Recurse with the new output, dropping the initial whitespace from the remainder.
Here’s what it looks like:
loop :: (String, String) -> String
loop ([], output) = output
loop (cs, output) =
-- Step 1: Separate next word from rest
let (nextWord, rest) = L.break isSpace cs
-- Step 2: Make new output (account for edge cases)
-- (Can’t use ‘combine’ from above because we aren’t reversing!)
newOutput = if null output then nextWord
else if null nextWord then output
else nextWord <> (' ' : output)
-- Drop spaces from remainder and recurse
in loop (L.dropWhile isSpace rest, newOutput)And completing the function is as simple as calling this loop with the base inputs:
reverseWords :: String -> String
reverseWords input = loop (input, “”)The Simplest Haskell Solution
The final (and recommended) Haskell solution uses the library functions words and unwords. These do exactly what we want for this problem! We separate words based on whitespace using words, and then join them with a single space with unwords. All we have to do in between is reverse.
reverseWords :: String -> String
reverseWords = unwords . reverse . wordsThis has a similar elegance to the advanced Rust solution, but is much simpler to understand since there are no complex structs or iterators involved. The types of all functions involved simply relate to lists. Here are the signatures, specialized to String for this problem.
words :: String -> [String]
reverse :: [String] -> [String]
unwords :: [String] -> StringConclusion
A simple problem will often have many solutions, but in this case, each of these solutions teaches us something new about the language we’re working with. Working character-by-character helps us understand some of the core mechanics of the language, showing us how it works under the hood. But using library functions helps us see the breadth of available options we have for simplifying future code we write.
In our Solve.hs course, you’ll go through all of these steps with Haskell. You’ll implement list library functions, data structures, and algorithms from scratch so you understand how they work under the hood. Then, you’ll know they exist and be able to apply them to efficiently solve harder problems. Take a look at the course today!