Refactoring with Applicatives in Haskell

This post demonstrates how to use the <$> (fmap) and <*> (sequential application) operators to refactor a function.

Let’s say we have a simple function to tell us if one string is an anagram of another string:

isAnagram :: String -> String -> Bool
isAnagram xs ys = sort xs == sort ys

In GHCI, we see how the function behaves:

λ> isAnagram "hello" "olleh"
True
λ> isAnagram "hello" "bye"
False

But let’s pretend the strings are represented as Maybe String. Perhaps they’re coming from user input and may not be present. Now, we want our function signature to be Maybe String -> Maybe String -> Maybe Bool. We can create a trivial (but kind of ugly) implementation that does this:

isAnagramMaybe :: Maybe String -> Maybe String -> Maybe Bool
isAnagramMaybe xs ys = case xs of
  Nothing -> Nothing
  Just s1 -> case ys of
    Nothing -> Nothing
    Just s2 -> return (isAnagram s1 s2)

The new isAnagramMaybe function returns Just with True or False if both strings are present. Otherwise, it returns Nothing:

λ> isAnagramMaybe (Just "hello") (Just "olleh")
Just True
λ> isAnagramMaybe (Just "hello") (Just "bye")
Just False
λ> isAnagramMaybe (Just "hello") Nothing
Nothing

However, there’s a concise way to implement this function:

isAnagramMaybe2 :: Maybe String -> Maybe String -> Maybe Bool
isAnagramMaybe2 xs ys = isAnagram <$> xs <*> ys

Let’s try to make sense of what’s going on here.

First, let’s examine <$>, which is called fmap:

λ> :i <$>
(<$>) :: Functor f => (a -> b) -> f a -> f b
  	-- Defined in ‘Data.Functor’

To get to the implementation of isAnagramMaybe2, let’s follow the types step-by-step. First, apply isAnagram to the fmap operator, <$>:

λ> :t (<$>) isAnagram
(<$>) isAnagram :: Functor f => f String -> f (String -> Bool)

By applying isAanagram to the <$> operator, Haskell infers the types for a and b. In this case a is String and b is String -> Bool.

Now we can apply the next argument of type Maybe String (and we can now use <$> as an infix operator):

λ> :t isAnagram <$> Just "hello"
isAnagram <$> Just "hello" :: Maybe (String -> Bool)

By applying Just "hello" Haskell infers that f represents a Maybe, so it leaves us with the last part of the function, which is Maybe (String -> Bool).

Now we can apply the sequential application operator, <*>. First, let’s examine its definition:

λ> :i <*>
class Functor f => Applicative (f :: * -> *) where
  ...
  (<*>) :: f (a -> b) -> f a -> f b
  ...
  	-- Defined in ‘GHC.Base’

Great! This operator takes a f (a -> b) and f a to give us f b. From the previous example, we now have a Maybe (String -> Bool) which fits the first part of the function. Let’s apply it:

λ> :t (<*>) (isAnagram <$> Just "hello")
(<*>) (isAnagram <$> Just "hello") :: Maybe String -> Maybe Bool

We’re almost there, now! All we need is a Maybe String to get our Maybe Bool. We’ve applied our first Maybe String, so let’s apply our second Maybe String (and use <*> as an infix operator):

λ> :t isAnagram <$> Just "hello" <*> Just "elloh"
isAnagram <$> Just "hello" <*> Just "elloh" :: Maybe Bool

Now we just parameterize this snippet to get the implementation of isAnagramMaybe2:

isAnagramMaybe2 :: Maybe String -> Maybe String -> Maybe Bool
isAnagramMaybe2 xs ys = isAnagram <$> xs <*> ys

Let’s make sure it works:

λ> isAnagramMaybe2 (Just "hello") (Just "elloh")
Just True
λ> isAnagramMaybe2 (Just "hello") (Just "bye")
Just False
λ> isAnagramMaybe2 (Just "hello") Nothing
Nothing

Great! It works!

Now that we’ve simplified the implementation, we can also get crazy and build an even-more generalized version that takes any Applicative of String and returns the same Applicative of Bool. We can do this using the liftA2 function provided in Control.Applicative:

import Control.Applicative

isAnagramMaybe3 :: Applicative a => a String -> a String -> a Bool
isAnagramMaybe3 = liftA2 isAnagram

λ> isAnagramMaybe3 (Just "hello") (Just "elloh")
Just True
λ> isAnagramMaybe3 (Just "hello") (Just "bye")
Just False
λ> isAnagramMaybe3 ["hello"] ["elloh"]
[True]
λ> isAnagramMaybe3 ["hello"] ["elloh", "bye"]
[True,False]
λ> isAnagramMaybe3 ["hello", "bye"] ["elloh", "eyb"]
[True,False,False,True]

Since List implements the Applicative typeclass, we can now use lists of strings to get the cross product of anagram comparisons!

Is this generalized implementation useful? Maybe. Is this fun? Definitely.