Haskell Refactoring Step-Through
by @mjgpy3 on October 31, 2023
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).
The first assignment is a simple string match. Essentially, given a list of
keywords, determine if any keyword is present in an input
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
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)
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
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
.) 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 :: (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
$ 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
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
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
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
bool :: a -> a -> Bool -> a bool f _ False = f bool _ t True = t
Let’s convert this to a
bool f t b = case b of False -> f True -> t
Bool is easily converted to an
else, be sure to flip
then t should come first, not
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?
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.