Flipping words in Haskell

The following was a very simple programming kata I ran through in Haskell and had fun with. It lends itself to a very natural solution with Monads.

I didn't see any other submission that took a monadic approach to this problem at all, so I thought I'd share. Here's the problem:

Write a function which takes a string as input, e.g. "hello, this is a sentence", and then outputs another string where each word (space delimited) longer than 5 characters is reversed. So for our example input, the output should be: ",olleh this is a ecnetnes".

In a procedural language, especially ones with excellent support for string manipulation like Python or Javascript, the most obvious approach is to split up the input string into words by splitting along " ", then walk through that list of words with a loop, with an if-block checking if the length of the word is long enough and then reversing it.

Of course, Haskell has enough syntactic sugar to do a list comprehension, or we could words our string and then walk through it with a foldl (or for perfomance's sake probably a foldr would be superior), concatenating at each step of the fold with either the next string or the reverse of the next string depending on your Boolean value. In the end, this solution would look a lot like a solution written in Python or Javascript, and it's the approach I saw taken in every other submission on the kata.

However, the best code in Haskell, in my opinion, doesn't just devolve back into simulating for loops and if blocks. Haskell reads cleanest when it starts with very simple functions, and then combines those functions in standard ways to build up bigger functions.

The thing about this style of programming is that the minute you start doing it, you immediately run into Monads.

Alright, let's get started. I'll be working in the interactive environment:

$ ghci
GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
Loaded package environment from ~/.ghc/x86_64-darwin-8.8.4/environments/default
Prelude>

The whole time, I'll be using ghci to check type annotations of expressions we write, using the :type command. Looking at how GHC interprets our type annotations will actually drive a lot of our coding: we're practicing type driven development, perhaps?

We only really need two basic functions here. We could probably do with less, but to keep it super clear, let's write two: condRev, which either reverses or doesn't reverse a string, depending on a Boolean parameter, and isLong, which takes an Int and a String and let's us know whether the string is longer than the int.

Prelude> condRev = \b s -> if b then reverse s else s
Prelude> :t condRev
condRev :: Bool -> [a] -> [a]

Prelude> isLong = flip ((>=) . length)
Prelude> :t isLong
isLong :: Foldable t => Int -> t a -> Bool

Now you might not notice it, but we're working already in a Monad! Specifically, we're in the (->) r monad. We'll need Control.Monad, so let's import it:

Prelude> import Control.Monad
Prelude Control.Monad>

The (->) r Monad is a context for computation where all the monadic objects are functions with an r input. For us, by the way, r is the parameterized type [a] in GHCi's type annotations above. Actually, for our problem we're specifically interested in [Char], or more readably, String.

How do we know we want to be in the (->) String Monad?

Well, isLong is a function taking an Int and a String and outputting a Bool, but we don't want to think about it that way: we'd rather think of it as a function taking an Int as a parameter, and then returning a function :: String -> Bool, i.e. a (->) String Bool. If we write m for our (->) String Monad, then we can write this as m Bool. It's a monadic Boolean.

Same thing for condRev. It's certainly a function that takes a Bool and a String and outputs a String, but we'd rather think of it as a function that takes a Bool and then outputs a function :: String -> String, i.e. a monadic string.

In short: the data we're really interested in manipulating is all parameterized by strings, so it makes sense to be in the (->) String Monad.

From our perspective inside the (->) String Monad, we think of isLong as a monadic function of type :: Int -> m Bool, and condRev as a monadic function of type :: Bool -> m String. We want to compose these two monadic functions and get a monadic function of type :: Int -> m String, so we use the Kleisli arrow:

Prelude Control.Monad> :t (>=>)
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c

Exactly what we want.

Prelude Control.Monad> condFlipWord = isLong >=> condRev
Prelude Control.Monad> :t condFlipWord
condFlipWord :: Int -> [a] -> [a]

What does condFlipWord do? Well, it takes an Int and outputs a monadic String, or rather, a function from String to String. Looking at the logic of isLong and condRev it's easy to see what their Kleisli composition does:

Prelude Control.Monad> condFlipWord 4 "jumping"
"gnipmuj"
Prelude Control.Monad> condFlipWord 10 "jumping"
"jumping"

Of course, we're not quite done. We wanted a function that didn't flip a whole string depending on the string's length, but rather operated on each individual word in the string.

It will be helpful to use the library function words. Let's check its type and play around with it:

Prelude Control.Monad> :t words
words :: String -> [String]
Prelude Control.Monad> words "this is a sentence"
["this","is","a","sentence"]

Now we're already running into another Monad, albeit likely a more familiar one.

Yep, it's [], the List monad. Of course, the functor for mapping functions into a List datatype is map. But we don't want to map our whole condFlipWords function there:

Prelude Control.Monad> :t map condFlipWord
map condFlipWord :: [Int] -> [[a] -> [a]]

Instead we just want to pass the String -> String output of our condFlipWord function, i.e. we just want to map the output of our function. In other words, we want to compose the output of condFlipWord with map:

Prelude Control.Monad> condFlipWords = map . condFlipWord
Prelude Control.Monad> :t condFlipWords
condFlipWords :: Int -> [[a]] -> [[a]]

Prelude Control.Monad> condFlipWords 5 (words "this is a sentence")
["this","is","a","ecnetnes"]

Of course, we also want to pre-compose our function with words so it will start with a string input, and post-compose with unwords so it returns the flattened string as output.

We just have to be careful about the position of arguments and where we apply the compositions:

Prelude Control.Monad> :t condFlipWords . words
<interactive>:1:17: error:
    • Couldn't match type ‘[String]’ with ‘Int’

Prelude Control.Monad> :t flip condFlipWords . words
flip condFlipWords . words :: String -> Int -> [[Char]]

Great! We also need to unwords it to get back from [[Char]] (i.e. [String]) to String.

Prelude Control.Monad> :t unwords . (flip condFlipWords . words)
<interactive>:1:12: error:
    • Couldn't match type ‘Int -> [[Char]]’ with ‘[String]’

Oops! Our final curried output of flip condFlipWords . words is of type :: [String], but the uncurried output is of type :: Int -> [String], which we can't plug into unwords. We only want to unwords the output. Again, that means a composition: in this case using (unwords .). Let's check its type first to make sure this operator makes sense to use:

Prelude Control.Monad> :t (unwords .)
(unwords .) :: (a -> [String]) -> a -> String

Yep! Exactly what we need. Let's verify we get the type we wanted when we compose:

Prelude Control.Monad> :t (unwords .) . (flip condFlipWords . words)
(unwords .) . (flip condFlipWords . words)
  :: String -> Int -> String

Perfect! Or almost: we'd rather flip the parameters back.

Prelude Control.Monad> condFlipSentence = flip $ (unwords .) . (flip condFlipWords . words)

Our particular problem statement considered words of length 5 or longer to be long, so with a bit of partial application:

Prelude Control.Monad> flipWords = condFlipSentence 5

Here's the final behavior of our function:

Prelude Control.Monad> flipWords "this is a sentence"
"this is a ecnetnes"

Here's the whole code:

import Control.Monad

condRev = \b s -> if b then reverse s else s
isLong = flip ((>=) . length)

condFlipWord = isLong >=> condRev

condFlipWords = map . condFlipWord

condFlipSentence = flip $ (unwords .) . (flip condFlipWords . words)

flipWords = condFlipSentence 5