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
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
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
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!