# Solving a few Leetcode questions in Haskell

Published:

Leetcode is a popular site which hosts a database of programming questions and crowd-sourced solutions in different programming lanuages. Recently, I decided to try my hand at solving some of these questions using Haskell, both to improve my skills in the language, and to prepare for future interviews, where I may or may not use Haskell. Unfortunately, Leetcode does not support using Haskell to submit answers, but I thought it would be fun nonetheless.

One of the difficulties with solving Leetcode questions with a functional langauge like Haskell is that most, if not all, solutions and explanations for a given question are presented in an imperative or object-oriented style. Despite this, I think that thinking functionally can often lead to incredibly elegant solutions to these problems, so I'd like to share some of these interesting ones here. I've also tried to ensure that the solutions are algorithmically efficent -- no brute force answers allowed. Let's jump in.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

In this question, we are given two lists of digits in reverse order and we need to return the list of digits of their sum. For example:

add [2, 4, 3] [5, 6, 4] -- 465 + 243
= [7, 0, 8] -- 807


Of course, the built-in list type in Haskell is a linked-list, which makes this questions particularly easy to handle.

Our strategy here will simply be to convert both lists to their decimal representation, then add them and convert the resulting sum back to a list of digits. This will take $O(n)$ time, but might not be particularly efficient due to the conversion back and forth. However, it means that we don't have to worry about carrying digits, or what to do when the lists are of different lengths.

First we need a toDecimal function, to convert from a digit list to an integer, which we define like this, using point-free style:

-- ex: [2, 4, 3] == 342 == 2*10^0 + 4*10^1 + 3*10^2
powersOfTen = [10 ^ n | n <- [0 ..]]
toDecimal = sum . zipWith (*) powersOfTen


Here we define a lazy, infinite list of all powers of 10. Then to convert to decimal, we multiply each digit with its corresponding power, then sum it up.

Next we need a fromDecimal function which will essentially act in reverse: given a number, produce its digits in a list in reverse order. Notice that we want to generate a list from a single value, which is exactly what the unfoldr function from Data.List is meant to do! 1

Recall that unfoldr is a higher-order function with the type

unfoldr :: (b -> Maybe (a, b)) -> b -> [a]


Essentially, it takes a starting value b, and a function that returns Nothing in its base case (when nothing more should be added to the list), and Just (a, b) in the recursive case. The first part of the tuple, a represents what should be added to the list, while the second part, b reprents the remainder of the value.

I admit, that sounds complicated, but an example should help. For fromDecimal n, the base case is when $n$ is $0$. Here, we add nothing to our result list. In the recursive case, we add $n \mod 10$ to the list, since this gives us the leading digit of $n$, and continue with $\lfloor n / 10 \rfloor$ as our remainder.

Finally, following precisely from this definition, in Haskell 2:

## Conclusion

So there are my Haskell solutions to these four Leetcode questions. I focused on list based questions in this one, but Haskell also excels at solving tree-based questions, with its support for algebraic data types and pattern matching. Overall, I think type-driven functional programming has a lot to offer for solving tricky problems like these, so give it a shot!

I hope you found these solutions interesting, but if you see a mistake or an improvement in any of these, please feel free to reach out via Twitter or email.

If you are hiring a software engineer intern for the summer of 2022, please reach out!

1

It shouldn't be too surprising that unfoldr is useful here, given that zipWith and sum, which we used in the complementary function, are really just specialized versions of foldr.

2

I'm using the LambdaCase language extension here.

3

Another approach would be to build a histiogram of the character counts for each string, then compare these for equality. This would be more efficient if you have a fast dictionary implementation, but this strategy does not fit so easily into our final solution, so I'll skip it for now.