Applicative wordcount 

Skipping over to section 6 of EIP “Modular programming with applicative functors.”


There is an additional benefit of applicative functors over monads, which concerns the modular development of complex iterations from simpler aspects. ….

As an illustration, we consider the Unix word-counting utility wc, which computes the numbers of characters, words and lines in a text file.

We can translate the full example using applicative function composition, which is only available on my personal branch. (PR #388 is pending)

Modular iterations, applicatively 

scala> import cats._,, cats.implicits._
import cats._
import cats.implicits._

scala> import Func.{ appFunc, appFuncU }
import Func.{appFunc, appFuncU}

The character-counting slice of the wc program accumulates a result in the integers-as-monoid applicative functor:

Here’s a type alias to treat Int as a monoidal applicative:

scala> type Count[A] = Const[Int, A]
defined type alias Count

In the above, A is a phantom type we don’t need, so let’s just hardcode it to Unit:

scala> def liftInt(i: Int): Count[Unit] = Const(i)
liftInt: (i: Int)Count[Unit]

scala> def count[A](a: A): Count[Unit] = liftInt(1)
count: [A](a: A)Count[Unit]

The body of the iteration simply yields 1 for every element:

scala> val countChar: AppFunc[Count, Char, Unit] = appFunc(count)
countChar:[Count,Char,Unit] =$$anon$6@4f7da1db

To use this AppFunc, we would call traverse with List[Char]. Here’s a quote I found from Hamlet.

scala> val text = ("Faith, I must leave thee, love, and shortly too.\n" +
                  "My operant powers their functions leave to do.\n").toList
text: List[Char] =
List(F, a, i, t, h, ,,  , I,  , m, u, s, t,  , l, e, a, v, e,  , t, h, e, e, ,,  , l, o, v, e, ,,  , a, n, d,  , s, h, o, r, t, l, y,  , t, o, o, .,
, M, y,  , o, p, e, r, a, n, t,  , p, o, w, e, r, s,  , t, h, e, i, r,  , f, u, n, c, t, i, o, n, s,  , l, e, a, v, e,  , t, o,  , d, o, .,

scala> countChar traverse text
res0: Count[List[Unit]] = Const(96)

This looks ok.

Counting the lines (in fact, the newline characters, thereby ignoring a final ‘line’ that is not terminated with a newline character) is similar: the difference is simply what number to use for each element, namely 1 for a newline and 0 for anything else.

scala> def testIf(b: Boolean): Int = if (b) 1 else 0
testIf: (b: Boolean)Int

scala> val countLine: AppFunc[Count, Char, Unit] =
         appFunc { (c: Char) => liftInt(testIf(c === '\n')) }
countLine:[Count,Char,Unit] =$$anon$6@318107a7

Again, to use this we’ll just call traverse:

scala> countLine traverse text
res1: Count[List[Unit]] = Const(2)

Counting the words is trickier, because it necessarily involves state. Here, we use the State monad with a boolean state, indicating whether we are currently within a word, and compose this with the applicative functor for counting.

scala> def isSpace(c: Char): Boolean = (c === ' ' || c === '\n' || c === '\t')
isSpace: (c: Char)Boolean

scala> val countWord =
         appFuncU { (c: Char) =>
           import{ get, set }
           for {
             x <- get[Boolean]
             y = !isSpace(c)
             _ <- set(y)
           } yield testIf(y && !x)
         } andThen appFunc(liftInt)
countWord:[[γ$3$][[X][cats.Eval,Boolean,X],Count,γ$3$],Char,Unit] =$$anon$6@19a4ff28

Traversing this AppFunc returns a State datatype:

scala> val x = countWord traverse text
x:[[X][cats.Eval,Boolean,X],Count,List[Unit]] = Nested(

We then need to run this state machine with an initial value false to get the result:

scala> x.value.runA(false).value
res2: Count[List[Unit]] = Const(17)

17 words.

Like we did with shape and content, we can fuse the traversal into one shot by combining the applicative functions.

scala> val countAll = countWord product countLine product countChar
countAll:[[α][[α][[γ$3$][[X][cats.Eval,Boolean,X],Count,γ$3$],Count,α],Count,α],Char,Unit] =$$anon$6@6176bbe2

scala> val allResults = countAll traverse text
allResults:[[α][[γ$3$][[X][cats.Eval,Boolean,X],Count,γ$3$],Count,α],Count,List[Unit]] = Prod(Prod(Nested(,Const(2)),Const(96))

scala> val charCount = allResults.second
charCount: Count[List[Unit]] = Const(96)

scala> val lineCount = allResults.first.second
lineCount: Count[List[Unit]] = Const(2)

scala> val wordCountState = allResults.first.first
wordCountState:[[X][cats.Eval,Boolean,X],Count,List[Unit]] = Nested(

scala> val wordCount = wordCountState.value.runA(false).value
wordCount: Count[List[Unit]] = Const(17)


Applicative functors have a richer algebra of composition operators, which can often replace the use of monad transformers; there is the added advantage of being able to compose applicative but non-monadic computations.

That’s it for today.