Composition of applicative functions

[Eugene Yokota]

Hi,

I've been obsessed about applicative composition since I read The Essence of Iterator Pattern (EIP) a few weeks ago. My original motivation was to learn about Traversable, but as I dug deeper I came to think Scalaz is missing a detail that can make it more useful. Let me know if I am on to something.

Here are two applicative functions f an g:

    scala> val f = { (x: Int) => x + 1 }

    f: Int => Int = <function1>

   

    scala> val g = { (x: Int) => List(x, 5) }

    g: Int => List[Int] = <function1>

We can use them to traverse List(1, 2, 3) for example:

    scala> List(1, 2, 3) traverseU f

    res0: Int = 9

    scala> List(1, 2, 3) traverseU g

    res1: List[List[Int]] = List(List(1, 2, 3), List(1, 2, 5), List(1, 5, 3), List(1, 5, 5), List(5, 2, 3), List(5, 2, 5), List(5, 5, 3), List(5, 5, 5))

EIP mentions operators that can be used to compose two applicative functions that returns another. These are provided so we can traverse the data structure once and get composed results:

    data (m ⊠ n) a = Prod { pfst::m a, psnd::n a }

    (⊗) :: (Functor m, Functor n) ⇒ (a → m b) → (a → n b) → (a → (m ⊠ n) b)

    (f ⊗ g) x = Prod(f x)(g x)

and

    data (m 􏰂 n) a = Comp { unComp::m (n a) }

    (⊙) :: (Functor n, Functor m) ⇒ (b → n c) → (a → m b) → (a → (m 􏰂 n) c)

    f ⊙ g = Comp ◦ fmap f ◦ g

Just looking at the signature, these look similar to &&& and <<< defined for Arrow, but the way it behaves as functor is different. For example, suppose we use &&& to compose f and g.

    scala> List(1, 2, 3) traverseU (f &&& g)

    res2: (Int, List[List[Int]]) = (9,List(List(1, 5), List(2, 5), List(3, 5)))

We get different results. I am guessing this is why Product and Composition were added.

It seems like we have a solution, but not quite. The private ProductApplicative is a typeclass instance, but it doesn't have a way of retaining itself as a value because it uses pair to hold the data as Applicative[({type λ[α] = (F[α], G[α])})#λ]. So we have half of ⊠, but we are missing the (⊗) operator.

Here's the from current [WorldCount][1] example:

    // To count, we traverse with a function returning 0 or 1, and sum the results

    // with Monoid[Int], packaged in a constant monoidal applicative functor.

    val Count = Monoid[Int].applicative

    // Compose the applicative instance for [a]State[Int,a] with the Count applicative

    val WordCount = StateT.stateMonad[Int].compose[({type λ[α] = Int})#λ](Count)

    // Fuse the three applicatives together in parallel...

    val A = Count

      .product[({type λ[α] = Int})#λ](Count)

      .product[({type λ[α] = State[Int, Int]})#λ](WordCount)

    // ... and execute them in a single traversal

    val ((charCount, lineCount), wordCountState) = A.traverse(text)((c: Char) => ((1, test(c == '\n')), atWordStart(c)))

First, the typeclass instances are composed, then implementation is manually put into pairs again.

The main problem I think is coming from the fact that there's no data type that's holding on to the typeclass instanes. Jason said this predates Unapply, so we can get some help from it too.

Similar to Kleisli arrows for monads, I've defined a data type called [AppFunc][2] in my topic/appfunc branch:

    trait AppFunc[F[_], A, B] { self =>

      def runA(a: A): F[B]

      implicit def F: Applicative[F]

      ...

    }

In there I define @>>>, <<<@, @&&&, and &&&@ operators that does the applicative composition. Let's see the f and g example first:

    scala> val f = AppFuncU { (x: Int) => x + 1 }

    f: scalaz.AppFunc[scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M,Int,Int] = scalaz.AppFuncFunctions$$anon$8@2ad4a8e3

    scala> val g = AppFuncU { (x: Int) => List(x, 5) }

    g: scalaz.AppFunc[scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M,Int,Int] = scalaz.AppFuncFunctions$$anon$8@51cd32b5

    scala> (f @&&& g) traverse List(1, 2, 3)

res3: (scalaz.Unapply[scalaz.Applicative,Int]{type M[X] = Int; type A = Int}#M[List[Int]], scalaz.Unapply[scalaz.Applicative,List[Int]]{type M[X] = List[X]; type A = Int}#M[List[Int]]) = (9,List(List(1, 2, 3), List(1, 2, 5), List(1, 5, 3), List(1, 5, 5), List(5, 2, 3), List(5, 2, 5), List(5, 5, 3), List(5, 5, 5)))

Now we get the same result as traversing f and g independently. Thanks to Unapply, no type annotations here either. And here's my rewrite of the [WordCount][3]:

    // To count characters, treat Int as monoidal applicative

    val countChar = AppFuncU { (c: Char) => 1 }

    // To count lines, treat Int as monoidal applicative

    val countLine = AppFuncU { (c: Char) => test(c === '\n') }

    // To count words, we need to detect transitions from whitespace to non-whitespace.

    val countWord = AppFuncU { (c: Char) =>

      for {

        x <- get[Boolean]

        val y = c =/= ' '

        _ <- put(y)

      } yield test(y && !x)

    } @>>> AppFuncU { (x: Int) => x }

    // Compose applicative functions in parallel

    val countAll = countWord @&&& countLine @&&& countChar

    // ... and execute them in a single traversal 

    val ((wordCountState, lineCount), charCount) = countAll traverse text

As you can see countAll, the composition is done once at the value level.

The type inference works for @&&& as long as the applicative function on the rhs are simple enough.

So, the above example works, but it's not perfect. Thoughts?

-eugene

  [1]: https://github.com/scalaz/scalaz/blob/c0f74398fdbc4f804fa06429fb58db4a9d3aafb0/example/src/main/scala/scalaz/example/WordCount.scala

  [2]: https://github.com/eed3si9n/scalaz/blob/topic/appfunc/core/src/main/scala/scalaz/AppFunc.scala

  [3]: https://github.com/eed3si9n/scalaz/blob/topic/appfunc/example/src/main/scala/scalaz/example/WordCount.scala

[etorreborre]

I just had a quick glance and that looks very promising.

I also had an unrelated idea, reading your code.

In the WordCount example, we have a function "flipping" the state of a boolean depending on a function:

val countWord = AppFuncU { (c: Char) =>

      for {

        x <- get[Boolean]

        val y = c =/= ' '

        _ <- put(y)

      } yield test(y && !x)

Wouldn't it be nice to have this as an abstraction? Does this exist in Haskell already? That would be something like

def flipWhen[T](condition: T => Boolean) = (t: T) =>

      for {

        x <- get[Boolean]

        val y = condition(t)

        _ <- put(y)

      } yield test(y && !x)

val countWord = AppFuncU { flipWhen((c: Char) => c =/= ' ')

Eric.

[Tony Morris]

On Sep 27, 2012 9:55 AM, "etorreborre" <etorr...@gmail.com> wrote:
>
> I just had a quick glance and that looks very promising.
>
> I also had an unrelated idea, reading your code.
>
> In the WordCount example, we have a function "flipping" the state of a boolean depending on a function:
>
> val countWord = AppFuncU { (c: Char) =>
>       for {
>         x <- get[Boolean]
>         val y = c =/= ' '
>         _ <- put(y)
>       } yield test(y && !x)
>
>
> Wouldn't it be nice to have this as an abstraction? Does this exist in Haskell already? That would be something like
>
> def flipWhen[T](condition: T => Boolean) = (t: T) =>

def flipWhen[T]: Store[T, Boolean] =>

> --
> You received this message because you are subscribed to the Google Groups "scalaz" group.
> To view this discussion on the web visit https://groups.google.com/d/msg/scalaz/-/hm9bzvvJzqQJ.
>
> To post to this group, send email to sca...@googlegroups.com.
> To unsubscribe from this group, send email to scalaz+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/scalaz?hl=en.

[eugene yokota]

Hi Ben,

I just saw this today. I guess it's been on the moderation queue?

On Wed, Oct 24, 2012 at 6:43 AM, Ben James <ben....@guardian.co.uk> wrote:
> I have also been reading EIP recently and this work is very interesting,
> thank you.
>
> Reading the WordCount example, it looks as if you have used the product
> operator to compose 3 monoidal applicatives into a new monoidal applicative.

countChar and countLine are monoidal applicative, but
countWord is a "sequential composition" of a monadic applicative and a
monoidal applicative.

> I would expect that the type of the monoids does not matter here, since
> their applicatives have a phantom type parameter.

This is correct.

> However, I think that @&&& is only working in this example because all 3
> functions return an Int. It won't work with arbitrary monoidal applicatives,
> e.g.
>
> scala> val f = AppFuncU { i: Int => i }
> scala> val g = AppFuncU { i: Int => String }
>
> scala> f @&&& h
> <console>:20: error: type mismatch;
> found :
> scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,java.lang.String]{type
> M[X] = java.lang.String; type A =
> java.lang.String}#M,scalaz.Applicative,Int,java.lang.String]
> required: scalaz.typelevel.Func[?,scalaz.Applicative,Int,Int]
> f @&&& h

I don't think there's problem with @&&&. It's just that AppFuncU is
not doing something you want it to do, which is to make an Int
applicative out of String.

scala> val g = AppFuncU { i: Int => i.toString }
g: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,java.lang.String]{type
M[X] = java.lang.String; type A =
java.lang.String}#M,scalaz.Applicative,Int,java.lang.String] =
scalaz.typelevel.FuncFunctions$$anon$12@9e6f48f

Without any type annotation, that's the best type inference can do.
Note U in AppFuncU stands for Unapply. You can force the issue by
using AppFunc {...} available in the latest scalaz-seven branch, and
supply type annotation as follows:

scala> val g2 = AppFunc[({type λ[α]=String})#λ, Int, Int] { i: Int
=> i.toString }
g2: scalaz.typelevel.Func[[α]java.lang.String,scalaz.Applicative,Int,Int]
= scalaz.typelevel.FuncFunctions$$anon$8@1908dbb8

We can then compose this with f, but you're not getting any type
inference love here:

scala> val f = AppFuncU { i: Int => i + 1 }
f: scalaz.typelevel.Func[scalaz.Unapply[scalaz.Applicative,Int]{type
M[X] = Int; type A = Int}#M,scalaz.Applicative,Int,Int] =
scalaz.typelevel.FuncFunctions$$anon$12@46b8b390

scala> f.@&&&[({type λ[α]=String})#λ](g2)
res5: scalaz.typelevel.HListFunc[scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type

M[X] = Int; type A =

Int}#M,scalaz.typelevel.TCCons[[α]java.lang.String,scalaz.typelevel.TCNil]],scalaz.Applicative,Int,Int]
= scalaz.typelevel.Func$$anon$4@4286f694

> The product that I want is the equivalent of:
>
> Monoid[Int].applicative.product[({type
> λ[α]=String})#λ](Monoid[String].applicative)
>
> Ben

res5 above is a function that returns the applicative product, except
it's using typelevel package instead of "product" method.

scala> res5 traverse List(1, 2, 3)
res6: scalaz.typelevel.TCCons[scalaz.Unapply[scalaz.Applicative,Int]{type

M[X] = Int; type A =

Int}#M,scalaz.typelevel.TCCons[[α]java.lang.String,scalaz.typelevel.TCNil]]#Product[List[Int]]
= GenericCons(9,GenericCons(123,GenericNil()))

- eugene