How I improve the readability of my Haskell code

Recently I've rediscovered my love for hackerrank.com while trying to get used to the Haskell programming language. This proved to be the best idea to learn the syntax of a language that I barely used in the past, and you might be surprised how much fun it is to solve easy programming questions in a totally different way.

Until, that is, I found myself tired and bored and tried to solve the Append an Delete problem. I think I was quite tired when I attempted to solve this question and I ended up with quite a horrible solution. A solution that works, but is quite ugly to look at. But before I show you my solution, let's explain the problem.

The problem I was trying to solve

The problem provides you with:

• An initial string of lowercase letters

• A target string to transform it into

• A specific number of moves you must use

For example, if you need to transform "hello" into "hi" in exactly 5 moves, you'd need to determine if this is possible using only these operations. Each deletion removes one character from the end, and each append adds one lowercase letter to the end. Even if your string becomes empty, you can still keep deleting (though this just maintains an empty string).

So, for this example, the steps will look like this:

"hello" -> "hell" -> "hel" -> "he" -> "h" -> "hi"

These being exactly the 5 number of moves we'd need. Let's look at another example. If we want to transform "hi" into "bye" in 6 moves, you'd do something like this:

"hi" -> "h" -> "" -> "" -> "b" -> "by" -> "bye"

Note that we use the remove character on the empty string so we can get the exact number of moves that we need.

Also, if the numbers have a common prefix we can delete until there and add the new suffix to the initial string. For example, if we want to transform "sell" into "self" we can check that the two strings have the same prefix "sel" and do the transformation in two moves:

"sell" -> "sel" -> "self"

But, if we wanted to do the same transformation in 4 steps instead we can remove one character from the preffx and re-add it.

"sell" -> "sel" -> "se" -> "sel" -> "self"

For 6 we can do the same. by removing the prefix until "s". Note that we can't do this transformation in exactly 7 moves because the add-remove pattern only works in increments of two, until that is, we end up with an empty string. For example, if we want to convert the same string using 9 moves you'd do:

"sell" -> "sel" -> "se" -> "s" -> "" -> "" -> "s" -> "se" -> "sel" -> "self"

This gives us a bit more insight on what strategy we need to take to check that we can do this string transformation in 3 ways:

1. Remove characters until the common root and the add the suffix of the target string

2. Remove characters until the common root and beyond (the remainder of operations has to be a multiple of 2)

3. Remove the initial String and completely rebuild it (applying remove on the empty string if necessary). This operation can be done for any k that is greater than the combined lengths of the two strings.

Initial solution

Now, let's see how I did on my initial attempt at writing the code for this method:

commonPrefix :: String -> String -> String
commonPrefix s t = map fst $ takeWhile (uncurry(==)) $ zip s t

solution :: String -> String -> Int -> Bool
solution s t k
    | commonPrefixLength == sl = 
            k == tDiff || (k > tDiff && (k - tDiff) `mod` 2 == 0) || (k > tDiff + 2 * sl)
    | commonPrefixLength == tl = 
            k == sDiff || (k > sDiff && (k - sDiff) `mod` 2 == 0) || (k > sl + tl)
    | otherwise                = 
            (k == totalDiff) || (k > totalDiff && (k - totalDiff) `mod` 2 == 0) || (k > sl + tl)
    where
        sl = length s
        tl = length t
        commonPrefixLength = length $ commonPrefix s t
        tDiff = tl - commonPrefixLength
        sDiff = sl - commonPrefixLength
        totalDiff = tDiff + sDiff

apply :: (String -> String -> Int -> Bool) -> [String] -> Bool
apply f str = f s t k
    where
        s = head str
        t = str !! 1
        k = read (str !! 2)

main = interact $ (\x -> if x then "Yes" else "No") . apply solution . words

This solution works, it validates 3 main cases:

1. The work string is contained in the target string

2. The target string contained in the work string

3. The work and target strings are not contained in each other

Improvement 1: Update your logic

When we call a code readable we understand that it can be read faster by someone who is generally familiar with the language but doesn't know all the intricacies of it. We want to stray away from complicated logic on one line or very "genius" code that requires 150+ IQ to read. That is not because we're expecting the readers to be dumb, but to we're expecting them to be able to read and fix any potential issue fast.

Usually the first step in any refactoring is to check that your logic is sound. This can save you a lot of reading time later. And this code is way too complicated for what it needs to do. For once, we actually don't need these 3 cases and we can do with only one if we do 2 simple observations:

1. These two statements are equivallent. This is because tl = (sl - tl)

tDiff + 2 * sl

sl + tl

2. Building on the previouse observation, the 3 branches have the same equation

So, we can update the code to only have one case (which will significantly reduce the reading time.

commonPrefix :: String -> String -> String
commonPrefix s t = map fst $ takeWhile (uncurry(==)) $ zip s t

solution :: String -> String -> Int -> Bool
solution s t k = 
    (k == totalDiff) || (k > totalDiff && (k - totalDiff) `mod` 2 == 0) || (k > sl + tl)
    where
        sl = length s
        tl = length t
        commonPrefixLength = length $ commonPrefix s t
        tDiff = tl - commonPrefixLength
        sDiff = sl - commonPrefixLength
        totalDiff = tDiff + sDiff

apply :: (String -> String -> Int -> Bool) -> [String] -> Bool
apply f str = f s t k
    where
        s = head str
        t = str !! 1
        k = read (str !! 2)

main = interact $ (\x -> if x then "Yes" else "No") . apply solution . words

Now we can take a look at the variables we're using in the solution method.

Improvement 2: Variable naming and use

Adding more variables to your code can make it more readable, provided the names are easy to understand. But even with proper naming, a lot of variables can create readability issues. It only depends on the use. My rule of thumb is, I'll use a variable if:

1. An equation is used in more than one place. This reduces the places you need to edit in case of a change

2. Adding a variable will make an computation shorter

In our case, initially, all the variables were used in multiple places in the 3 equations so we could argue their use. But now there are just too many variable to count and having them in only one equation shouldn't affect readability.

solution :: String -> String -> Int -> Bool
solution s t k = 
    (k == totalDiff) || (k > totalDiff && (k - totalDiff) `mod` 2 == 0) || (k > totalLength)
    where
        commonPrefixLength = length $ commonPrefix s t
        totalLength = length t + length s
        totalDiff = totalLength - 2 * commonPrefixLength

[Haskell specific] Improvement 3: List comprehension

One last readability update we can make is actually getting rid of the apply function. It's too verbose for what we want to do and it can be replaced by a lambda with list comprehension.

I tend to use similar rules for when I want to use a method as when I want to create a variable. If I have the same logic in two places or if having the method would aid the readability of the code.

In our case, the apply method is too verbose and its equivalent is much easier to read in a function composition.

So, let's see the final iteration of the code:

commonPrefix :: String -> String -> String
commonPrefix s t = map fst $ takeWhile (uncurry(==)) $ zip s t

solution :: String -> String -> Int -> Bool
solution s t k = 
    (k == totalDiff) || (k > totalDiff && (k - totalDiff) `mod` 2 == 0) || (k > totalLength)
    where
        commonPrefixLength = length $ commonPrefix s t
        totalLength = (length t) + (length s)
        totalDiff = totalLength - 2 * commonPrefixLength

main = interact 
     $ (\x -> if x then "Yes" else "No") 
     . (\[s, t, k] -> solution s t (read k)) 
     . words 

Conclusion

Thanks for reading through my initially badly written code and walked with me while I try to make it better. These is the life of a code, first you write it badly but it works then you optimize the readability.

To summarize:

1. Fix your logic

2. Fix your variables

3. Fix your methods