The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Composition of applicative functions
 There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic. There was an error processing your request. Please try again. Standard view   View as tree
 5 messages

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Sep 26 2012, 4:55 pm
From: Eugene Yokota <eed3s...@gmail.com>
Date: Wed, 26 Sep 2012 13:55:46 -0700 (PDT)
Local: Wed, Sep 26 2012 4:55 pm
Subject: Composition of applicative functions

Hi,

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
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

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 26 2012, 7:55 pm
From: etorreborre <etorrebo...@gmail.com>
Date: Wed, 26 Sep 2012 16:55:28 -0700 (PDT)
Local: Wed, Sep 26 2012 7:55 pm
Subject: Re: Composition of applicative functions

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

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

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.

To post a message you must first join this group.
You do not have the permission required to post.
More options Sep 26 2012, 7:59 pm
From: Tony Morris <tonymor...@gmail.com>
Date: Thu, 27 Sep 2012 09:59:11 +1000
Local: Wed, Sep 26 2012 7:59 pm
Subject: Re: [scalaz] Re: Composition of applicative functions

On Sep 27, 2012 9:55 AM, "etorreborre" <etorrebo...@gmail.com> wrote:

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

> 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

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

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

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.

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

>> 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.

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]:

the rhs are simple enough.
>> So, the above example works, but it's not perfect. Thoughts?

>> -eugene

>>   [1]:

https://github.com/scalaz/scalaz/blob/c0f74398fdbc4f804fa06429fb58db4...
>>   [2]:

https://github.com/eed3si9n/scalaz/blob/topic/appfunc/core/src/main/s...
>>   [3]:

https://github.com/eed3si9n/scalaz/blob/topic/appfunc/example/src/mai...

> --
> You received this message because you are subscribed to the Google Groups
"scalaz" group.
> To view this discussion on the web visit

> To post to this group, send email to scalaz@googlegroups.com.
> To unsubscribe from this group, send email to

> For more options, visit this group at

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 24 2012, 6:43 am
From: Ben James <ben.ja...@guardian.co.uk>
Date: Wed, 24 Oct 2012 03:43:08 -0700 (PDT)
Local: Wed, Oct 24 2012 6:43 am
Subject: Re: Composition of applicative functions

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.

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

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]{t ype
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

The product that I want is the equivalent of:

Monoid[Int].applicative.product[({type
λ[α]=String})#λ](Monoid[String].applicative)

Ben

To post a message you must first join this group.
You do not have the permission required to post.
More options Oct 30 2012, 11:29 pm
From: eugene yokota <eed3s...@gmail.com>
Date: Tue, 30 Oct 2012 23:29:33 -0400
Local: Tues, Oct 30 2012 11:29 pm
Subject: Re: [scalaz] Re: Composition of applicative functions
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.ja...@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]{t ype
> 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]{t ype
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.Ap plicative,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