Today I thought it'd be fun to take a look at a few common & simple "interview questions" in Haskell. These sorts of questions are often used to establish whether someone has programming and problem solving skills, and I thought it might be useful for folks to see how they play out in Haskell since our beloved language's solutions tend to follow a different paradigm than most other languages do. I'll withhold any judgement on whether these questions are in any way helpful in determining programming skill whatsoever 😅; please don't @ me about it.
Palindromes
Let's start off nice and easy with the standard "is it a palindrome" question! The task is to write a function which determines whether a given string is a palindrome (i.e. whether it reads the same in both reverse and forwards)
isPalindrome :: String -> Bool
isPalindrome str = str == reverse str
>>> isPalindrome "racecar"
True
>>> isPalindrome "hello world!"
FalseThat'll do it! Not much to say about this one, it's nice that our definition roughly matches an English sentence describing the problem "does a given string equal itself in reverse". I'll leave it as an exercise for the reader to expand it to handle differences in capitalization however you like.
Fizz Buzz
Next up is the infamous Fizz Buzz! For the 3 of you who are unfamiliar, for each number from 1 to 100 we need to print out "Fizz" if it's divisible by 3, "Buzz" if it's divisible by 5, and "Fizz Buzz" if it's divisible by both 3 AND 5! Otherwise we print the number itself.
Let's see it!
import Data.Foldable
fizzle :: Int -> String
fizzle n
| n `mod` 3 == 0 && n `mod` 5 == 0 = "Fizz Buzz!"
| n `mod` 3 == 0 = "Fizz!"
| n `mod` 5 == 0 = "Buzz!"
| otherwise = show n
main :: IO ()
main = do
for_ [1..100] (putStrLn . fizzle)
>>> main
1
2
Fizz!
4
Buzz!
Fizz!
7
8
Fizz!
Buzz!
11
Fizz!
13
14
Fizz Buzz!
16
-- ...you get the ideaI write a helper function "fizzle" here which converts a number into its appropriate string so I can keep the "printing" logic separate, which is good programming style in Haskell as it makes things easier to both test and reason about.
We can see that "case analysis" is very helpful for these sorts of problems, I'm using "pattern guards" to do a sort of multi-way if statement. Since "divisible by both 3 & 5" overlaps with the other conditions and also is the most restrictive, we check for that one first, then check the other two cases falling back on returning the string version of the number itself. It all works beautifully!
I really enjoy looking at this problem as an example of how Haskell is different from other languages. Most things in Haskell are functions, even our loops are just higher-order functions! The nice thing about that is that functions are composable and have very clean boundaries, which means we don't need to intermingle the syntax of a for-loop with our logic. It's these same principles which allow us to easily separate our effectful printing logic from our function which computes the output string.
The next difference we can see is that we use pattern-matching, specifically "pattern guards", which allow us to select which definition of a function we want to use. It looks a bit like a glorified if-statement, but I find it's less syntactic noise once you get used to it, and there are many more things pattern guards can do!
All that's left is to loop over all the numbers and print them out
one by one, which is a snap thanks to the for_
function!
Next!
Sum up to N problem
Here's a less-common problem that nonetheless I've still heard a few times! I think it was in one of my algorithms assignments back in the day...
The task is to take a list of numbers and find any combinations of 3 numbers which add up to a specified total. For instance, if we want to determine all combinations of 3 numbers which add up to 15, we'd expect our result to look something like this:
>>> sumToN 15 [2, 5, 3, 10, 4, 1, 0]
[[2,3,10],[5,10,0],[10,4,1]]Notice how each inner list sums to 15? We only care about
combinations here, not permutations, so we have
[2, 3, 10], but don't bother with
[3, 2, 10]!
So how will we set about implementing an algorithm for this? Well, the first thing to come to mind here is that we're finding combinations, then we're filtering them down to match a predicate!
In Haskell we like to split problems into smaller composable pieces, the filter part should be pretty easy, so let's tackle the combinations problem first.
After a quick look through hackage it looks like there is a
permutations
function, but strangely there's no combinations function! I
suppose we could somehow try to de-duplicate the output of
permutations, but it'll be fun to write our own version!
combinations are quite nice to compute recursively, so
let's try it that way!
combinations :: Int -> [a] -> [[a]]
-- Only one way to get zero things
combinations 0 _ = [[]]
combinations n (x:xs) =
-- Get all combinations containing x by appending x to all (n-1)
-- combinations of the rest of the list
fmap (x:) (combinations (n-1) xs)
-- Combine it with all combinations from the rest of the list
<> combinations n xs
-- No elements means no combinations!
combinations _ [] = []Here we're using pattern matching and recursion to do our dirty work.
First we can confidently say that there's only ONE way to get 0 elements
from any list of elements, so we can fill that in. Next
we'll handle a single step, if we have at least one element left in the
list, we can compute all the combinations which contain that element by
prepending it to all the combinations of size n-1 from the
remainder of the list; and we'll concatenate that with all the
combinations of the rest of the list.
Lastly we add one more pattern match which handles all invalid inputs (either negative numbers or empty lists) and simply assert that they have no valid combinations.
Let's try out our implementation before we move on to the next part.
>>> combinations 3 [1..5]
[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]
>>> combinations 2 [1..4]
[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]Feel free to take the time to convince yourself that these are correct 😀
To finish it off we need to find any of these combinations which add up to our target number.
sumNToTotal :: Int -> Int -> [Int] -> [[Int]]
sumNToTotal n totalNeeded xs =
filter matchesSum (combinations n xs)
where
matchesSum ys = sum ys == totalNeeded
>>> sumNToTotal 3 15 [2, 5, 3, 10, 4, 1, 0]
[[2,3,10],[5,10,0],[10,4,1]]Great! We can simply get all possible combinations and filter out the results which don't properly sum to the expected number. One other nifty thing here is that, because Haskell is lazy, if we only need to find the first valid combination, we could just grab the first result of the list and Haskell won't do any more work than absolutely necessary.
But wait! There's a surprise part two of this problem:
We now have to find all combinations of ANY length which sum to a target number, lucky for us, that's pretty easy for us to adapt for!
sumAnyToTarget :: Int -> [Int] -> [[Int]]
sumAnyToTarget totalNeeded xs
= foldMap (\n -> sumNToTotal n totalNeeded xs) [0..length xs]
>>> sumAnyToTarget 15 [2, 5, 3, 10, 4, 1, 0]
[ [5,10]
, [2,3,10]
, [5,10,0]
, [10,4,1]
, [2,3,10,0]
, [10,4,1,0]
, [2,5,3,4,1]
, [2,5,3,4,1,0]
]This new version re-uses the sumNToTotal function we
wrote in the previous step! It iterates over each possible length of
combination and finds all the winning combinations using
sumNToTotal, then concatenates them using
foldMap! Works out pretty cleanly if I do say so
myself!
Check if two strings are anagrams
For whatever reason, interviewers LOVE string manipulation questions; so let's try another one!
Here our task is to determine whether two strings are anagrams of each other. I'd say the difficulty for this one comes from thinking up your strategy rather than the implementation itself. Here's how I'd give this a go in Haskell!
import Data.Function (on)
isAnagram :: String -> String -> Bool
isAnagram = (==) `on` sort
>>> isAnagram "elbow" "below"
True
>>> isAnagram "bored" "road"
False
>>> isAnagram "stressed" "desserts"
TrueHere we're using a funky higher-order function called
on; on takes two functions, AND THEN takes two
arguments! In this case it calls "sort" on both arguments, then checks
if the sorted results are equal! It turns out this is sufficient to know
if two strings are anagrams!
But wait! What's that? What if they're in differing cases! Okay fine!
import Data.Char (toLower)
isAnagram :: String -> String -> Bool
isAnagram a b = (==) `on` (sort . map toLower)Happy now? No? What's that? It seems non-performant? Well yes, but actually no!
While it's true that sort has an O(nlogn) performance
profile, one interesting thing here is that sorting is
lazy in Haskell! This means that if our two strings are
unequal, they will only be sorted far enough to determine inequality! In
fact, if the first elements of each sorted string aren't equal to each
other, then we won't bother sorting any more.
Sure, our function isn't perfect, but it's not bad, especially since this is the first approach that came to mind. Compare our 2 line solution with the Java Solution provided in the post which gave me the idea for this problem. It might be more performant (though to be honest I haven't benchmarked them), but if I'm going to be reading this code often in the future, I'd much prefer the clearest version which performs at an adequate level.
Min and Max
Here's a problem! Given a list of elements, find the smallest and largest element of that list!
I'll show and discuss three different strategies for this one.
Here's the first:
simpleMinMax :: Ord a => [a] -> (a, a)
simpleMinMax xs = (minimum xs, maximum xs)
>>> simpleMinMax [3, 1, 10, 5]
(1,10)This is the simplest way we could imagine doing this sort of thing; and indeed it does work! Unfortunately, there are few skeletons from "legacy" haskell that are hidden in this closet. Look what happens if we try it on an empty list!
>>> simpleMinMax []
(*** Exception: Prelude.minimum: empty listOops... Haskell isn't supposed to throw exceptions! That's okay though, there are some other good ways to accomplish this which won't blow up in our faces!
Time for the next one!
boundedMinMax :: (Bounded a, Ord a) => [a] -> (a, a)
boundedMinMax xs = coerce $ foldMap (\x -> (Min x, Max x)) xs
>>> boundedMinMax [4, 1, 23, 7] :: (Int, Int)
(1,23)
>>> boundedMinMax [] :: (Int, Int)
(9223372036854775807,-9223372036854775808)This implementation might be a bit confusing if you haven't learned enough about Semigroups and Monoids, but don't let that scare you! These are both very common abstractions in Haskell and are used very often and to great effect!
A Semigroup is a type of interface which provides an implementation
which lets us combine multiple elements together. Haskell has two
semigroup type-wrappers which provide specific behaviour to whichever
type we wrap: Min and Max!
These types define a combining operation which, any time we combine
two elements, will keep only the smallest or largest value respectively!
I'm using foldMap here to project each list element into a
tuple of these two types which, when the list is collapsed by
foldMap, will all combine together and will include the
lowest and highest elements, all in a single pass!
So what's up with the second example? Well, it's a bit unexpected,
but not necessarily wrong. When we're missing any elements to
compare foldMap will use the default value for each of our type
wrappers, which it can do if they're monoids. For Min and
Max the default value is the "smallest" and "largest" value
of the wrapped type, which is defined by the Bounded
interface that we require in the type signature. This works okay, and
behaves as expected under most circumstances, but maybe we can
try one more time:
import Data.Semigroup
minMax :: Ord a => [a] -> Maybe (a, a)
minMax xs = case foldMap (\a -> Just (Min a, Max a)) xs of
Just (Min x, Max y) -> Just (x, y)
_ -> Nothing
>>> minMax [4, 1, 9, 5]
Just (1,9)
>>> minMax []
NothingOkay! This is pretty much the same, but we needed an
explicit way to correctly handle an empty list of
values. In this case, by wrapping our tuple in Just we
invoke the Maybe monoid, and remember that
foldMap is smart enough to return the "empty" element of
that monoid if our list is empty! That means we get Nothing
back if there are no elements.
This may seem like "magic" at first, but all of these typeclasses have laws which dictate their behaviour and make them predictable. I suggest learning more about monoids if you have time, they're fascinating and useful!
This is a very "safe" implementation, in fact much safer than most
languages would offer. We explicitly return Nothing in the
case that the list is empty, and the Maybe return type
requires the caller to handle that case. I mentioned earlier how
functions are composable, and it turns out that data-types are too! If
we pair two objects with a semigroup together in a tuple, that tuple has
a semigroup instance too, which combines respective element together
when we combine tuples!
Word Frequency
This is a pretty popular one too!
The challenge this time is, given a block of text, find the most common word!
Ultimately, this comes down to an understanding of data-structures.
import Data.List (maximumBy)
import Data.Function (on)
import qualified Data.Map as M
mostCommonWord :: String -> Maybe String
mostCommonWord str =
if null wordCounts
then Nothing
else Just . fst . maximumBy (compare `on` snd) . M.toList $ wordCounts
where
wordCounts = M.unionsWith (+) . fmap (\w -> M.singleton w 1) . words $ strThere's a bit more going on this time, so let's break it down a bit!
In Haskell, we use "math-style" function composition using
., so we read most expressions from right-to-left.
Let's look at the wordCounts binding down in the
where clause first. Reading from right to left, first we
use the words function from the built-in Prelude to split
the incoming stream into a list of words, then we create a key-value map
out of each one, consisting of the word as the key with a value of
1 to start.
Now we have a list of key-value maps, and can add them up all up
key-wise using unionsWith from the Data.Map
library, this will count up the number of elements of each key and will
result in a key-value mapping where the values represent
occurrences.
We've got a mapping now, so let's find the largest count!
First things first, to be safe we'll check whether the map has any
values at all, if it doesn't then we'll return Nothing.
Otherwise, we can convert the map into a list of key-value pairs by
calling M.toList, then we can use maximumBy to
return the biggest element according to a comparison function that we
specify! on comes in handy here and we can tell it to
compare on the second element, which is the count. That will return us
the key-value pair with the largest value, then we just need to grab the
key as a result using fst!
Ultimately this is a bit of a naive implementation which won't work well on huge texts, but it should be enough to get you through the whiteboard portion of the interview 😄.
Summary
That's all I've got for you today, nothing to revolutionary I'm sure, but hopefully you had a bit of fun, or maybe learned a thing or two about what code looks like in Haskell compared to your favourite language 😄
Hopefully you learned something 🤞! If you did, please consider checking out my book: It teaches the principles of using optics in Haskell and other functional programming languages and takes you all the way from an beginner to wizard in all types of optics! You can get it here. Every sale helps me justify more time writing blog posts like this one and helps me to continue writing educational functional programming content. Cheers!