Comparing Code: LeetCode Problems in Rust vs. Haskell

May 19

Today will be the first in a series where we’ll be exploring some LeetCode problems and comparing different solutions from Haskell and Rust. The main idea is to demonstrate how you might translate ideas between the recursive core of Haskell, and the loop-based framing of most other languages.

If you want to learn more about problem solving in Haskell, you should take a closer look at Solve.hs! This course will give you an in-depth walkthrough of problem solving ideas in Haskell, including how concepts compare to more typical languages.

The Problem

The first problem we’ll consider is called H-Index. In academia, a person has an “H-Index” of n if they have published at least n papers that have n or more citations. So the input to our problem is a list of integers, where each integer is the number of citations of a particular paper the author wrote. Our job is to calculate the author’s H-Index.

The Algorithm

This problem is fairly straightforward if you sort the input list. Once we do this, we can look at any index i, and consider the number of remaining entries (e.g. n - i), and we’ll know that the number of papers with at least that many citations is n - i.

So we can accomplish this task with a single loop over the sorted list. Throughout this loop, we’ll be tracking the maximum “H-Index” we’ve seen so far (maxH). At each iteration, we take the following steps:

Get the number of remaining papers (rem) and the citations at this index (next) If the rem is greater than next, then update maxH to next if next is larger. Otherwise, update maxH to rem if rem is greater.

The last step is a key edge case! If we have the list [1, 1, 1, 9, 9], we’ll get to index 3, with next being 9 and rem being 2. The remainder is smaller than the index, but we would still update maxH to 2, because there are at least 2 citations remaining that are 2 or greater.

Rust Solution

Here’s our Rust solution:

pub fn h_index(citations: Vec<i32>) -> i32 {
    let mut cp = citations.clone();
    cp.sort();
    let n = cp.len();
    let mut maxH: i32 = 0;
    for i in 0..n {
        let next = cp[i];
        let rem: i32 = (n - i) as i32;
        if (rem >= next) {
            maxH = std::cmp::max(next, maxH);
        } else {
            maxH = std::cmp::max(rem, maxH);
        }
    }
    return maxH;
}

We have the first part, where we clone the input, sort it, and set up our loop variables:

pub fn h_index(citations: Vec<i32>) -> i32 {
    let mut cp = citations.clone();
    cp.sort();
    let n = cp.len();
    let mut maxH: i32 = 0;
    ...
}

Then we have the loop itself, where we have our two cases to consider:

for i in 0..n {
    let next = cp[i];
    let rem: i32 = (n - i) as i32;
    if (rem >= next) {
        // There are at least ‘next’ papers >= ‘next’
        maxH = std::cmp::max(next, maxH);
    } else {
        // ‘next’ > ‘rem’, so there are at least ‘rem’ papers >= ‘rem’
        maxH = std::cmp::max(rem, maxH);
    }
}

So this is pretty straightforward. Now how do we approach this kind of problem in Haskell?

Haskell Solution

Our Haskell solution will have the same structure, but instead of running a loop and indexing into a vector, we’ll use a linked list and call a recursive function. Let’s begin by getting the length and sorting our input:

import qualified Data.List as L

hIndex :: [Int] -> Int
hIndex inputs = ...
  where
    n = length inputs
    sorted = L.sort inputs

    ...

Now we need to think about our recursive loop function. At each iteration, we need access to the remaining number of values, the next citation value, and we need to pass along maxH. As with many list-based recursive functions, we’ll peel off one element of the input list each time. Ultimately we’ll return maxH from this loop when we hit our base case of an empty input list. So its type signature should look like this:

loop :: (Int, [Int], Int) -> Int

When writing a recursive function, we always handle the base case first:

loop :: (Int, [Int], Int) -> Int
loop (_, [], maxH) = maxH

Now in the recursive case, we can apply our algorithm, updating maxH if necessary:

loop :: (Int, [Int], Int) -> Int
loop (_, [], maxH) = maxH
loop (remaining, next : rest, maxH) = if remaining >= next
  then loop (remaining - 1, rest, max next maxH)
  else loop (remaining - 1, rest, max remaining maxH)

To finish up, all we need to do is call our loop function with the appropriate initial inputs (n, sorted, 0). Here’s our complete Haskell solution:

import qualified Data.List as L

hIndex :: [Int] -> Int
hIndex inputs = loop (n, sorted, 0)
  where
    n = length inputs
    sorted = L.sort inputs

    loop :: (Int, [Int], Int) -> Int
    loop (_, [], maxH) = maxH
    loop (remaining, next : rest, maxH) = if remaining >= next
      then loop (remaining - 1, rest, max next maxH)
      else loop (remaining - 1, rest, max remaining maxH)

Using a Fold

Now we can notice that our loop has a particular structure. We have one piece of accumulated state (maxH), and this changes based on each value in our list (combined with the remaining values). We can easily re-imagine this kind of loop using a fold. We just have to think of the folding function like this:

loop :: Int -> (Int, Int) -> Int
loop maxH (remaining, next) = if remaining >= next
  then max next maxH
  else max remaining maxH

This has the a -> b -> a structure of a left-fold function, where a is our accumulated maxH value, and the other values come from our list. The main benefit here is that our loop function no longer has to deal with the burden of calling a base case or passing the “shrinking” list as an argument to the next recursive call.

We can invoke this loop at the top level like so:

hIndex :: [Int] -> Int
hIndex inputs = foldl loop 0 (zip [n,n-1..1] sorted)
  where
    n = length inputs
    sorted = L.sort inputs

    loop :: Int -> (Int, Int) -> Int
    loop maxH (remaining, next) = if remaining >= next
      then max next maxH
      else max remaining maxH

We just have to zip the decreasing indices together with our sorted list. Now our recursive “loop” is more like a typical for-loop. We’re only considering one element at a time, and we’re updating the important state each time.

Conclusion

In this comparison, we saw a good comparison between a normal for-loop in Rust, and a recursive solution in Haskell. We also saw how we could simplify this recursive formulation into a “fold” structure.

If you're interested in learning more about writing recursive functions in Haskell, check out our Solve.hs course. You’ll learn how to start thinking about problems in a functional way, and you’ll learn the step-by-step processes for tackling problems with basic recursion and folds like we saw in this example.

James Bowen