Applicative wordcount 

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

EIP:

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.instances.all._
import cats._
import cats.instances.all._

scala> import cats.data.{ Func, AppFunc, Const }
import cats.data.{Func, AppFunc, Const}

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: cats.data.AppFunc[Count,Char,Unit] = cats.data.Func$$anon$6@666c81aa

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> import cats.syntax.eq._
import cats.syntax.eq._

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: cats.data.AppFunc[Count,Char,Unit] = cats.data.Func$$anon$6@2506c434

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 cats.data.State.{ get, set }
           for {
             x <- get[Boolean]
             y = !isSpace(c)
             _ <- set(y)
           } yield testIf(y && !x)
         } andThen appFunc(liftInt)
countWord: cats.data.AppFunc[[γ]cats.data.Nested[[X]cats.data.StateT[cats.Eval,Boolean,X],Count,γ],Char,Unit] = cats.data.Func$$anon$6@4063d8a4

Traversing this AppFunc returns a State datatype:

scala> val x = countWord traverse text
x: cats.data.Nested[[X]cats.data.StateT[cats.Eval,Boolean,X],Count,List[Unit]] = Nested(cats.data.StateT@3b411e74)

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: cats.data.AppFunc[[α]cats.data.Prod[[α]cats.data.Prod[[γ]cats.data.Nested[[X]cats.data.StateT[cats.Eval,Boolean,X],Count,γ],Count,α],Count,α],Char,Unit] = cats.data.Func$$anon$6@2f9df938

scala> val allResults = countAll traverse text
allResults: cats.data.Prod[[α]cats.data.Prod[[γ]cats.data.Nested[[X]cats.data.StateT[cats.Eval,Boolean,X],Count,γ],Count,α],Count,List[Unit]] = Prod(Prod(Nested(cats.data.StateT@6cb709d0),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: cats.data.Nested[[X]cats.data.StateT[cats.Eval,Boolean,X],Count,List[Unit]] = Nested(cats.data.StateT@6cb709d0)

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

EIP:

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.