6
\$\begingroup\$

I wrote this module to find the Hamming distance between two strings. (It's a problem from exercism.io's Haskell track.)

As I saw it, the problem has two distinct parts: check if the length of the two strings are equal (if not return Nothing), and recursive pattern matching on equal-length strings.

Since my score is a monad (Maybe), I didn't know how to implement the recursive adding without dealing with the Nothing case, so I broke it off into a separate function using a simple Int type.

GHC raises warning: [-Wincomplete-patterns] since my pattern matching in the helper function is incomplete. So:

  1. Is it bad practice to ignore this warning?
  2. Would it be better to implement the recursive part on the Maybe?
  3. Is there a better way to solve this problem?

I'm very new to Haskell, all help appreciated.

module Hamming (distance) where

distance :: String -> String -> Maybe Int
distance a b
  | length a /= length b = Nothing
  | otherwise = Just $ getDistance a b

getDistance :: String -> String -> Int
getDistance [] [] = 0
getDistance [x] [y] = if x == y then 0 else 1
getDistance (x : xs) (y : ys) = getDistance [x] [y] + getDistance xs ys
\$\endgroup\$
0
10
\$\begingroup\$

When you have a function where not every possible input value can be mapped to one of the possible output values, you have three options: Allow fewer inputs, allow more outputs, or declare that your function is partial rather than total and just isn't well-behaved sometimes.

  • The first is arguably the most flexible, but often involves some awkward re-shaping of your data. In this case that would mean a function that takes two strings that are guaranteed to be the same length somehow and definitely returns an Int. Can we do that? Well, we may be able to do something similar, but we'll get to that later. I'll call that function hamming just to give it a name
  • The second is a good middle ground, and it's our current mission. distance :: String -> String -> Maybe Int. This is slightly weaker than the first option, because you can use hamming to define distance, but not necessarily the other way around. Still, this is often easier to write, and a bit less awkward to use.
  • The third is by far the easiest to do, but it also means your function becomes harder to reason about in some ways. If I ever use a partial function like this getDistance :: String -> String -> Int, the computer doesn't know whether my use of it is well-behaved or not until it actually tries it because, well, all the computer knows is that sometimes that function doesn't play nice. Proving that some combination of non-total functions is itself total is hard, so if we can start from total functions it becomes easy (or at least easier) to convince both ourselves and the computer that the code does what we want it to do.

Type safety is like a wall, and partial functions are holes in that. There's definitely a place for making holes in walls, I appreciate fromJust, undefined, and infinite recursion, just like how I appreciate doorways. But if you have too many holes it doesn't really keep the wind out anymore, even though you'll probably still find it blocking your view.

So, can we write this code so that a computer can trust that it's total and type-safe? Well, the type of distance doesn't seem to be making any promises we can't keep, so it should be possible. Let's start with something like getDistance and see where we can end up

distance :: (Eq a) => [a] -> [a] -> Maybe Int

Notice the switch from String to Eq a => [a] - we can afford to be less specific here because we don't actually do anything with that specificity. There's no reason we need to work with [Char] in particular after all

distance [] [] = Just 0
distance [] _ = Nothing
distance _ [] = Nothing

Those are some simple cases with obvious outcomes, so let's make those our base cases. Now let's try some recursion. But how?

Well, pattern matching is easy to read and write, and effective, so we could just do a case split

distance (x : xs) (y : ys) =
    case (distance xs ys) of
        Nothing -> Nothing
        Just d -> Just ((if x == y then 0 else 1) + d)

Or we can take advantage of how Maybe is a Functor and do something fancier like

distance (x : xs) (y : ys) = fmap f (distance xs ys)
    where f = if x == y then (+ 0) else (+ 1)

Either way, we have a perfectly fine distance function. And this time it's total, which makes the computer slightly happier.

But what was that other thing I said earlier? Can we really have a function which takes two lists that are guaranteed to be the same size? Because that sounds useful!

Well, kind of. It just looks a bit different than you might expect

hamming :: (Eq a) => [(a, a)] -> Int
hamming [] = 0
hamming ((a, b) : rest) = (if a == b then 0 else 1) + (hamming rest)

Is that cheating? Maybe a bit, but it's still useful. A list of pairs is exactly the same as a pair of equal-length lists in terms of the stuff they're made of anyway, they're just in a slightly different shapes. And if we have two zipped list we can get their hamming distance without having to worry about Maybe at all and still be completely type-safe. Neat!

\$\endgroup\$
5
\$\begingroup\$

To address your title question ("Is it wrong..."), no, I wouldn't say that it's wrong. Using more top-level functions is nearly always a great way to decompose your problem into smaller, easier to digest bits that are simpler to solve. That said the split that you chose to make doesn't meet that goal. Your functions are tightly coupled in that distance relies on getDistance to provide an answer, and getDistance relies on distance to prepare its arguments correctly. A slightly better version might be to move getDistance into a where-clause underneath distance.

Regarding your numbered questions—

  1. I consider it a tenet of good practice to not ignore any warnings emitted by the compiler. The moment you do so you begin training your brain to ignore all warnings emitted by the compiler, and you'll eventually miss something meaningful because it's buried in the noise of compiler barf.

  2. "the recursive part on the Maybe?" I don't think this maps well grammatically to how you should be conceptualizing return values. The fact that Maybe is an instance of Monad doesn't actually come up in your code, you just use it as a pure value. See below for other ways to solve problems when your intermediary values are a mismatch for your return values.

  3. There are many ways I could imagine solving this problem, better is going to be a function of how robust you want your code to be, what dependencies you are comfortable adding, how clever (read: tricky) you feel comfortable leaving your code, and more.

What follows are a bunch of lightly commented solutions, demonstrating different ways of approaching the problem.

hamming :: Eq a => [a] -> [a] -> Int
hamming [] [] = 0
hamming (x:xs) (y:ys) = (if x == y then 0 else 1) + hamming xs ys
hamming _ _ = error "hamming: Can't compute Hamming distance of lists of different length"

This version just makes the strings being of equal length a precondition. We make the type of the function less specific because it helps us not write the wrong implementation (e.g., all you know about two a values is whether or not they're Eq here, but if you know you have Strings you could compare on letter case or anything else).

hamming :: Eq a => [(a, a)] -> Int
hamming [] = 0
hamming ((x, y) : xys) = (if x == y then 0 else 1) + hamming xys

This version makes it incumbent on the caller to provide a list of pairs, instead of a pair of lists. Now it's not possible to have mismatched lengths.

safeHamming :: Eq a => [a] -> [a] -> Maybe Int
safeHamming [] [] = Just 0
safeHamming (x:xs) (y:ys) = (+ if x == y then 0 else 1) <$> safeHamming xs ys
safeHamming _ _ = Nothing

This version uses fmap (<$> is fmap infix) to increment the returned value of the sub-problem (i.e. the shorter rest of the string). It uses the Functorness of Maybe, but still not the Monad instance.

safeHamming :: Eq a => [a] -> [a] -> Maybe Int
safeHamming = go 0
  where
    go d [] [] = Just d
    go d (x:xs) (y:ys) = go (d + if x == y then 0 else 1) xs ys
    go _ _ _ = Nothing

Sometimes an accumulator value is easier to work on than a return value.


What would be really great is if we could eliminate the explicit recursion in our solution altogether, leveraging existing functions to both avoid having to write as much code and to make our function easier for future readers to understand. Something like—

hamming :: Eq a => [a] -> [a] -> Int
hamming = length . filter id . zipWith (==)

But as clever as that function is, Haskell's standard zips all silently ignore when the lengths of the lists are mismatched by discarding the tail of the longer list. For a coding exercise (i.e. throwaway code) I'd probably just use that version though.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.