Haskell Refactoring Step-Through

Notice: This website has moved to a new URL. Please visit us at Renaissance Learning R&D.

Haskell Refactoring Step-Through

by @mjgpy3 on October 31, 2023

Background

Growing new Haskellers up to a point of productivity seems hard. But does it have to be?

Frecklers are always on the lookout for ways to level up our Haskell skills. We’ve run book clubs (going through Haskell Book and Maybe Haskell), had code sharing sessions and code reading discussions, paired often, and tried many more approaches!

Upon reflection some senior Haskellers concluded that, though these approaches have value, we’ve learned the most from our Haskell side projects. So, in an effort to pedagogically apply this learning strategy, we’ve starting a “Learn Haskell by Building” series. It’ll be a series of cumulative assignments that gradually introduce the language, tooling, and idioms. The idea is that this will create a space for newer Haskellers to grow familiar with the language and give more advanced/intermediate Haskellers a space to explore (e.g. new libraries, approaches).

First Assignment

The first assignment is a simple string match. Essentially, given a list of keywords, determine if any keyword is present in an input String.

The heart of my implementation looks like

-- | Represents the results of a match
data MatchResult
    = -- | Match found
      HasMatch
    | -- | No match found
      Doesn'tHaveMatch

keywords :: [String]
keywords = ["Freckle", "Rulez"]

-- | Try to find 'keywords' in the given argument
match :: String -> MatchResult
match haystack
    | any (`isInfixOf` haystack) keywords = HasMatch
    | otherwise = Doesn'tHaveMatch

Playing around with alternative implementations, I came up with a fun point-free version (bool is from Data.Bool)

match =
   bool Doesn'tHaveMatch HasMatch
     . (`any` keywords)
     . flip isInfixOf

In this “simple” function there are a ton of interesting Haskellisms at play. In order to understand them, let’s informally convert this, step-by-step, to more beginner-friendly Haskell.

For the simplification, I’d recommend

following along in your editor (if you’re a beginner or want some practice or fun)
thinking of what you’d do differently (if you’re more advanced), and
keeping Hoogle handy (since we’ll be using some definition substitution)

Simplification

Okay, first things first, let’s get rid of the point-free stuff by introducing an argument. To make this clear, let’s wrap the body in parenthesis

match =
-   bool Doesn'tHaveMatch HasMatch
+   (bool Doesn'tHaveMatch HasMatch
     . (`any` keywords)
-     . flip isInfixOf
+     . flip isInfixOf)

We can now introduce an argument and immediately apply the function to it

-match =
+match haystack =
   (bool Doesn'tHaveMatch HasMatch
     . (`any` keywords)
-     . flip isInfixOf)
+     . flip isInfixOf) haystack

Since what we have is a function (in parens) and an argument, we can replace the parens with $

match haystack =
-  (bool Doesn'tHaveMatch HasMatch
+  bool Doesn'tHaveMatch HasMatch
    . (`any` keywords)
-    . flip isInfixOf) haystack
+    . flip isInfixOf $ haystack

Now we have $ application of a bunch of “glued together” functions (composed with .) on the left. Let’s just use application everywhere!

match haystack =
  bool Doesn'tHaveMatch HasMatch
-    . (`any` keywords)
+    $ (`any` keywords)
-    . flip isInfixOf $ haystack
+    $ flip isInfixOf $ haystack

Exercise for the reader: reason through how f . g $ x and f $ g $ x are the same… Use signatures/hoogle.

The definition of flip is

flip                    :: (a -> b -> c) -> b -> a -> c
flip f x y              =  f y x

which can be written using lambdas instead of function arguments

flip = \f x y -> f y x

Let’s go ahead and replace flip with this definition

  bool Doesn'tHaveMatch HasMatch
    $ (`any` keywords)
-    $ flip isInfixOf $ haystack
+    $ (\f x y -> f y x) isInfixOf $ haystack

Now we can manually apply the lambda to isInfixOf by simple substitution

  bool Doesn'tHaveMatch HasMatch
    $ (`any` keywords)
-    $ (\f x y -> f y x) isInfixOf $ haystack
+    $ (\x y -> isInfixOf y x) $ haystack

Let’s do the same thing to haystack (since $ is just application after all)

  bool Doesn'tHaveMatch HasMatch
    $ (`any` keywords)
-    $ (\f x y -> f y x) isInfixOf $ haystack
+    $ (\y -> isInfixOf y haystack)

Okay! Now, to get rid of the lambda, let’s extract a where binding

  bool Doesn'tHaveMatch HasMatch
    $ (`any` keywords)
-    $ (\y -> isInfixOf y haystack)
+    $ infixOfHaystack
+  where
+    infixOfHaystack y = isInfixOf y haystack

any is applied as a backtick-section, meaning it’s effectively just a flip (since keywords is on the right).

We can either (1) make it into a flip or (2) wrap it in a lambda. Let’s do the latter

  bool Doesn'tHaveMatch HasMatch
-    $ (`any` keywords)
+    $ (\x -> x `any` keywords)
    $ infixOfHaystack
  where
    infixOfHaystack y = isInfixOf y haystack

We can get rid of the backticks (which allow any to be an infix), by moving any to prefix location

  bool Doesn'tHaveMatch HasMatch
-    $ (\x -> x `any` keywords)
+    $ (\x -> any x keywords)
    $ infixOfHaystack
  where
    infixOfHaystack y = isInfixOf y haystack

Let’s manually apply the lambda

  bool Doesn'tHaveMatch HasMatch
-    $ (\x -> any x keywords)
-    $ infixOfHaystack
+    $ any infixOfHaystack keywords
  where
    infixOfHaystack y = isInfixOf y haystack

bool is defined in Data.Bool as

bool :: a -> a -> Bool -> a
bool f _ False = f
bool _ t True  = t

Let’s convert this to a case expression

bool f t b =
  case b of
    False -> f
    True -> t

A case of Bool is easily converted to an if / else, be sure to flip order (i.e. then t should come first, not then f)

bool f t b = if b then t else f

Time to lambda-ify

bool = \f t b -> if b then t else f

Subbing this in gives

-  bool Doesn'tHaveMatch HasMatch
+  (\f t b -> if b then t else f) Doesn'tHaveMatch HasMatch
    $ any infixOfHaystack keywords
  where
    infixOfHaystack y = isInfixOf y haystack

Manually applying the arguments, one-by-one, gives

\t b -> if b then t else Doesn'tHaveMatch
\b -> if b then HasMatch else Doesn'tHaveMatch
if any infixOfHaystack keywords then HasMatch else Doesn'tHaveMatch

Which gives us, re-formatted for readability

match :: String -> MatchResult
match haystack =
  if any infixOfHaystack keywords
    then HasMatch
    else Doesn'tHaveMatch
  where
    infixOfHaystack y = isInfixOf y haystack

And there we go! Fun huh?

Conclusion

Though this example may seem trivial, it cuts to the core of Haskell’s power. We applied a series of small changes to transform a function without altering its behavior!

These tactics blur the line between the software engineering practice of refactoring and algebraic simplification. Not only is this extremely cool but it’s a microcosm of something greater. Safe refactoring practices scale from the simplest functions (like match) to our largest codebases.