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:
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.
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:
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
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?
On Thursday, September 27, 2012 6:55:46 AM UTC+10, Eugene Yokota wrote:
> 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
> 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.
> 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:
> 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?
> for {
> x <- get[Boolean]
> val y = condition(t)
> _ <- put(y)
> } yield test(y && !x)
> val countWord = AppFuncU { flipWhen((c: Char) => c =/= ' ')
> Eric.
> On Thursday, September 27, 2012 6:55:46 AM UTC+10, Eugene Yokota wrote:
>> 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.
>> 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.
>> 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
>> // 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?
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
On Wednesday, 26 September 2012 21:55:46 UTC+1, Eugene Yokota wrote:
> 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
> 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.
> 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:
> 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?
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
