Cats: Improve doc for Func

[tpolecat]

Nobody knows what the hell Func does ... linking to a 25-page Haskell paper (even a good one) isn't ideal. Can we improve the doc, at least to the point of explaining why we need both Func and Kleisli and how you might use it?

There is some discussion here.

[arosien]

Eugene goes into the rationale in herding-cats, day 11.

[kamilkloch]

I am still trying to understand the mechanics of the AppFunc with its embedded Applicative instance.

@eed3si9n in herding-cats, day 11 shows two benefits of AppFunc:

• product,
• nested andThen.

If I am not mistaken, neither of these make use of the Applicative instance. In fact, the only need for Applicative seems to be in AppFunc.traverse.

Below AppFunc with Applicative instance removed (getting closer to Kleisli). Please take a look. Thanks!
https://github.com/typelevel/cats/compare/master...kamilkloch:func-2650?expand=1

[eed3si9n]

Here's sudoku solved using Func - http://eed3si9n.com/sudoku-using-func
The point of AppFunc is that you can compose a bunch of together, and then call traverse on it once.

[kamilkloch]

Why can't one use Kleislis traverse for that? The only difference between AppFunc.traverse and Kleisli.traverse is in the way the Applicative instance is provided - in AppFunc it is baked into the type and in Kleisli it has to be provided with traverse.

Can't all AppFunc's functionality be provided within Kleisli? (I see only problematic nested andThen).

[eed3si9n]

Here's from herding cats, day 11:

An applicative function is a function in the form of A => F[B] where F forms an Applicative. This is similar to Kleisli composition of monadic functions, but _better_.

Here’s why. Kliesli composition will let you compose A => F[B] and B => F[C] using andThen, but note that F stays the same. On the other hand, AppFunc composes A => F[B] and B => G[C].

Using Tuple2K and Nested some typeclass instances F1 can be composed with another F2. Writing that code out by hand is tedious, you can derive complicated one automatically using AppFunc.

scala> val f = Func.appFunc { x: Int => List(x.toString + "!") }
f: cats.data.AppFunc[List,Int,String] = cats.data.Func$$anon$6@a6b56dd
scala> val g = Func.appFunc { x: Int => (Some(x.toString + "?"): Option[String]) }
g: cats.data.AppFunc[Option,Int,String] = cats.data.Func$$anon$6@2d0f032f
scala> val h = f product g
h: cats.data.AppFunc[[α]cats.data.Tuple2K[List,Option,α],Int,String] = cats.data.Func$$anon$6@625084a0

The types gets more messy if we compose multiple levels. See word count.

scala> type Count[A] = Const[Int, A]
scala> val countChar: AppFunc[Count, Char, Unit]  = ...
scala> val countLine: AppFunc[Count, Char, Unit] = ...
scala>     val countWord =
     |       appFunc { (c: Char) =>
     |         for {
     |           x <- get[Boolean]
     |           y = !isSpace(c)
     |           _ <- set(y)
     |         } yield testIf(y && !x)
     |       }.andThen(appFunc(liftInt))
countWord: cats.data.AppFunc[[γ$3$]cats.data.Nested[[A]cats.data.IndexedStateT[cats.Eval,Boolean,Boolean,A],Count,γ$3$],Char,Unit] = cats.data.Func$$anon$6@5b1c2405

scala> val countAll = countWord.product(countLine).product(countChar)
countAll: cats.data.AppFunc[[α]cats.data.Tuple2K[[α]cats.data.Tuple2K[[γ$3$]cats.data.Nested[[A]cats.data.IndexedStateT[cats.Eval,Boolean,Boolean,A],Count,γ$3$],Count,α],Count,α],Char,Unit] = cats.data.Func$$anon$6@3cb9532f

At the end of the day the return type is still in the form of Char => F[Unit] where F satisfies Applicative, so we can call traverse.

[kamilkloch]

As an experiment, I made WordCountSuite work without AppFunc, only with Kleisli. Following addition to Kleisli was needed:

  def product[G[_]](g: Kleisli[G, A, B]): Kleisli[λ[α => Tuple2K[F, G, α]], A, B] = {
    Kleisli[λ[α => Tuple2K[F, G, α]], A, B] { a: A =>
      Tuple2K(self.run(a), g.run(a))
    }
  }

  def composeNested[G[_], C](g: Kleisli[G, C, A])(implicit G: Functor[G]): Kleisli[Nested[G, F, ?], C, B] = {
    Kleisli[Nested[G, F, ?], C, B]({ c: C =>
      Nested(G.map(g.run(c))(self.run))
    })
  }

  def andThenNested[G[_], C](g: Kleisli[G, B, C])(implicit F: Functor[F]): Kleisli[Nested[F, G, ?], A, C] =
    g.composeNested(self)

So, summing up:

• Kleisli.traverse works fine (just like AppFunc.traverse),
• Kleisli.product works fine (just like AppFunc.product),
• Kleisli.andThenNested works fine, albeit the method name is weird (andThen being taken).

Does this justify the addition of AppFunc?

https://github.com/typelevel/cats/compare/master...kamilkloch:func-2650?expand=1

[eed3si9n]

Doesn't the name Kleisli come from Kleisli arrow in the Kleisli category F traditionally known as "Monad", and FlatMap in Cats? The point of Kleisli category is that it's a subcategory of Functor (endofunctor). With endofunctors, you stay in the same F.

The applicative function composition needs strictly weaker constraint, and it's more powerful because we are talking about typelevel F and G composition. So I'd ask the same question. Does this justify the addition of Kleisli?