Apply me both lists

Originally posted on dev.to/gillchristian.

Apply me both lists

As we saw in the previous one, Applicative allows to apply n-ary functions in a context. The context might be a parser, values that are potentially be errors, a list or a tree, optional values, IO actions, etc.

In my short learning experience so far, I've used it in practice for two things mostly.

Constructing values with data constructors that take several values. For example, those values would come from sequential parsers when working with parser combinators (like Parsec).

data User = User String String Int

-- "John Doe 26" -> User "John" "Doe" 26
parseUser :: Parser User
parseUser =
  User <$> (parseWord <* whitespace)
       <*> (parseWord <* whitespace)
       <*> parseAge

parseWord :: Parser String
parseAge :: Parser Int

whitespace :: Parser () -- consumes as much whitespace as possible

-- Defined in Control.Applicative
(<*) :: Applicative f => f a -> f b -> f a

(<*) is the lifted version of const, here is something I wrote about that. As we can guess from the signature, in this case it applies both parses (ie. both consume input) but returns the first one, ignoring the second.

And the other use case, applying n-ary functions to values that might not be there. In other words, when the context is Either or Maybe.

add <$> (Just 1) <*> (Just 2) -- Just 3
add <$> Nothing  <*> (Just 2) -- Nothing
add <$> (Just 1) <*> Nothing  -- Nothing
add <$> Nothing  <*> Nothing  -- Nothing

add <$> (Right 1)      <*> (Right 2)      -- Right 3
add <$> (Left "err 1") <*> (Right 2)      -- Left "err 1"
add <$> (Right 1)      <*> (Left "err 2") -- Left "err 2"
add <$> (Left "err 1") <*> (Left "err 2") -- Left "err 1"

Lists

Until last week I hadn't found a use case for Applicative when working with lists. I knew how it works but never had ~~an excuse~~ a reason to use it.

Let's take a look at the instance and some examples first.

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

-- With [] applied to f (using TypeApplications extension)
(<*>) @[] :: [a -> b] -> [a] -> [b]

(+) <$> [1, 2, 3] <*> [1, 2, 3]
-- [2,3,4,3,4,5,4,5,6]

(,) <$> [1, 2, 3] <*> [1, 2, 3]
-- [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

[(++ "!"), (++ "?")] <*> ["Hola", "Mundo"]
-- ["Hola!","Mundo!","Hola?","Mundo?"]

As we can see, it takes a list of functions ([a -> b]) and a list values ([a]) and applies all the functions from the first list to all the values from the second one, this results in a larger list (duh!). If list sizes are n and m, respectively, the size of the returned list is n * m.

That's not a use case that I find very often. Most of the time I have one function (a -> b) that I want to apply to a list of values ([a]). That's Functor's fmap (as well as (<$>)). Or I have a list of functions to apply to a single value. For example, it could be list of predicates and I want to check if all or some are True for a particular value.

allPass :: [a -> Bool] -> a -> Bool

anyPass :: [a -> Bool] -> a -> Bool

By the way, there are similar functions defined in Base:

and :: [Bool] -> Bool -- True when all are True

or :: [Bool] -> Bool  -- True when at least one is True

In the case of lists, what applicative does is apply all the functions too all the values.

Last week, playing around on small side project, till. I was trying to add the option to match several patterns against the same value and I found a use case for List's Applicative.

There's a match function that checks if a pattern matches a single line of the output.

match :: Pattern -> Line -> Bool

The output consists of a list of lines. When working with a single pattern, the solution is easy. Use any (from Base).

any :: Foldable t => (a -> Bool) -> t a -> Bool

any @[] :: (a -> Bool) -> [a] -> Bool

matchPattern :: Pattern -> [Line] -> Bool
matchPattern p lns = any (match p) lns

What about matching several patterns against the output?

matchAll :: [Pattern] -> [Line] -> Bool
matchAll ps lns = undefined -- ???

Applicative to the rescue 🎉

matchAll :: [Pattern] -> [Line] -> Bool
matchAll ps lns = or (match <$> ps <*> lns)

Let's dissect that :mag:

-- So we don't forget ;)
(<$>) @[] :: (a -> b) -> [a] -> [b]
   
(<*>) @[] :: [a -> b] -> [a] -> [b]

-- ^ notice the difference between <$> & <*> ;)

or :: [Bool] -> Bool

match :: Pattern -> Line -> Bool

-- the input
ps :: [Pattern]

lns :: [Line]

-- mapping first to partially apply the patterns to match
match <$> ps :: [Line -> Bool]

-- applying the lines
match <$> ps <*> lns :: [Bool]

-- reducing that to get our result
or (match <$> ps <*> lns) :: Bool

I like how elegant this looks thanks to Functor and Applicative 🎩

NOTE: I'm sure there are other ways to solve the problem, with better performance. Although in my use case both lists should be relatively short, usually between one and three patterns and around 100 or probably less lines of output.

Happy and safe coding 🦄