day 14
Yesterday we looked at what import scalaz._ and Scalaz._ bring into the scope, and also talked about a la carte style import. Knowing how instances and syntax are organized prepares us for the next step, which is to hack on Scalaz.
mailing list
Before we start hacking on a project, it’s probably good idea to join its Google Group.
git clone
$ git clone -b series/7.1.x git://github.com/scalaz/scalaz.git scalaz
The above should clone series/7.1.x branch into ./scalaz directory. Next I edited the .git/config as follows:
[core]
repositoryformatversion = 0
filemode = true
bare = false
logallrefupdates = true
ignorecase = true
[remote "upstream"]
fetch = +refs/heads/*:refs/remotes/origin/*
url = git://github.com/scalaz/scalaz.git
[branch "series/7.1.x"]
remote = upstream
merge = refs/heads/series/7.1.x
This way, scalaz/scalaz is referenced using the name upstream instead of origin. To track the changes, run:
$ git pull --rebase
Current branch series/7.1.x is up to date.
sbt
Next, launch sbt 0.13.5, set scala version to 2.11.1, switch to core project, and compile:
$ sbt
scalaz> ++ 2.11.1
Setting version to 2.11.1
[info] Set current project to scalaz (in build file:/Users/eed3si9n/work/scalaz/)
scalaz> project core
[info] Set current project to scalaz-core (in build file:/Users/eed3si9n/work/scalaz/)
scalaz-core> compile
This might take a few minutes. Let’s make sure this builds a snapshot version:
scalaz-core> version
[info] 7.0-SNAPSHOT
To try out the locally compiled Scalaz, just get into the REPL as usual using console:
scalaz-core> console
[info] Starting scala interpreter...
[info]
Welcome to Scala version 2.10.1 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_33).
Type in expressions to have them evaluated.
Type :help for more information.
scala> [Ctrl + D to exit]
including Vector
Let’s address some of the things we’ve noticed in the last few weeks. For example, I think Vector instances should be part of import Scalaz._. This should be easy while my memory is fresh from yesterday’s import review. Let’s make a topic branch topic/vectorinstance:
$ git branch topic/vectorinstance
$ git co topic/vectorinstance
Switched to branch 'topic/vectorinstance'
To confirm that Vector instances and methods are not loaded in by import Scalaz._, let’s check it from sbt console:
$ sbt
scalaz> ++ 2.11.1
scalaz> project core
scalaz-core> console
scala> import scalaz._
import scalaz._
scala> import Scalaz._
import Scalaz._
scala> Vector(1, 2) >>= { x => Vector(x + 1)}
<console>:14: error: could not find implicit value for parameter F0: scalaz.Bind[scala.collection.immutable.Vector]
Vector(1, 2) >>= { x => Vector(x + 1)}
^
scala> Vector(1, 2) filterM { x => Vector(true, false) }
<console>:14: error: value filterM is not a member of scala.collection.immutable.Vector[Int]
Vector(1, 2) filterM { x => Vector(true, false) }
^
Failed as expected.
Update std.AllInstances by mixing in VectorInstances:
trait AllInstances
extends AnyValInstances with FunctionInstances with ListInstances with MapInstances
with OptionInstances with SetInstances with StringInstances with StreamInstances
with TupleInstances with VectorInstances
...
Update syntax.std.ToAllStdOps and add ToVectorOps:
trait ToAllStdOps
extends ToBooleanOps with ToOptionOps with ToOptionIdOps with ToListOps with ToStreamOps with ToVectorOps
...
That’s it. Let’s try it from REPL.
scala> Vector(1, 2) >>= { x => Vector(x + 1)}
res0: scala.collection.immutable.Vector[Int] = Vector(2, 3)
scala> Vector(1, 2) filterM { x => Vector(true, false) }
res1: scala.collection.immutable.Vector[Vector[Int]] = Vector(Vector(1, 2), Vector(1), Vector(2), Vector())
It works. I didn’t see tests written for these type of things, so we’ll go without one. I committed it as “include VectorInstances and ToVectorOps to import Scalaz._.” Next, fork scalaz project on github.
$ git remote add fork git@github.com:yourname/scalaz.git
$ git push fork topic/vectorinstance
...
* [new branch] topic/vectorinstance -> topic/vectorinstance
Send a pull request with some comments, and let’s see what happens. To work on a next feature, we want to rewind back to scalaz-seven branch. For using locally, let’s create a snapshot branch:
snapshot
$ git co scalaz-seven
Switched to branch 'scalaz-seven'
$ git branch snapshot
$ git co snapshot
$ git merge topic/vectorinstance
We can use this branch as a sandbox to play around with Scalaz.
<*> operator
Next, I’d really like to roll back <*> operator for Apply back to M2/Haskell behavior. I’ve asked this on the mailing list and the author seems to be ok with rolling back.
$ git co scalaz-seven
Switched to branch 'scalaz-seven'
$ git branch topic/applyops
$ git co topic/applyops
Switched to branch 'topic/applyops'
This one we really should write a test first. Let’s add an example in ApplyTest:
"<*>" in {
some(9) <*> some({(_: Int) + 3}) must be_===(some(12))
}
The specs used in build.scala works for Scala 2.9.2.
$ sbt
scalaz> ++ 2.9.2
Setting version to 2.9.2
scalaz> project tests
scalaz-tests> test-only scalaz.ApplyTest
[error] /Users/eed3si9n/work/scalaz-seven/tests/src/test/scala/scalaz/ApplyTest.scala:38: type mismatch;
[error] found : org.specs2.matcher.Matcher[Option[Int]]
[error] required: org.specs2.matcher.Matcher[Option[(Int, Int => Int)]]
[error] some(9) <*> some({(_: Int) + 3}) must be_===(some(12))
[error] ^
[error] one error found
[error] (tests/test:compile) Compilation failed
It didn’t even compile because of ===. Nice.
The <*> is in ApplyOps, so let’s change it back to F.ap:
final def <*>[B](f: F[A => B]): F[B] = F.ap(self)(f)
Now let’s run the test again:
scalaz-tests> test-only scalaz.ApplyTest
[info] ApplyTest
[info]
[info] + mapN
[info] + apN
[info] + <*>
[info]
[info] Total for specification ApplyTest
[info] Finished in 5 seconds, 27 ms
[info] 3 examples, 0 failure, 0 error
[info]
[info] Passed: : Total 3, Failed 0, Errors 0, Passed 3, Skipped 0
[success] Total time: 9 s, completed Sep 19, 2012 1:57:29 AM
I am committing this as “roll back <*> as infix of ap” and pushing it out.
$ git push fork topic/applyops
...
* [new branch] topic/applyops -> topic/applyops
Send a pull request with some comments. Let’s apply this to our snapshot branch:
$ git co snapshot
$ git merge topic/applyops
So now it has both of the changes we created.
applicative functions
The changed we made were so far simple fixes. From here starts an experiment. It’s about applicative functions.
The Essence of the Iterator Pattern presents an interesting idea of combining applicative functors. What’s actually going on is not just the combination of applicative functors (m ⊠ n), but the combination of applicative functions:
(⊗)::(Functor m,Functor n) ⇒ (a → m b) → (a → n b) → (a → (m ⊠ n) b)
(f ⊗ g) x = Prod (f x) (g x)
Int is a Monoid, and any Monoid can be treated as an applicative functor, which is called monoidal applicatives. The problem is that when we make that into a function, it’s not distinguishable from Int => Int, but we need Int => [α]Int.
My first idea was to use type tags named Tags.Monoidal, so the idea is to make it:
scala> { (x: Int) => Tags.Monoidal(x + 1) }
This requires all A @@ Tags.Monoidal where [A:Monoid] to be recognized as an applicative. I got stuck on that step.
Next idea was to make Monoidal an alias of Kleisli with the following companion:
object Monoidal {
def apply[A: Monoid](f: A => A): Kleisli[({type λ[+α]=A})#λ, A, A] =
Kleisli[({type λ[+α]=A})#λ, A, A](f)
}
This let’s me write monoidal functions as follows:
scala> Monoidal { x: Int => x + 1 }
res4: scalaz.Kleisli[[+α]Int,Int,Int] = scalaz.KleisliFunctions$$anon$18@1a0ceb34
But the compiler did not find Applicative automatically from [+α]Int:
scala> List(1, 2, 3) traverseKTrampoline { x => Monoidal { _: Int => x + 1 } }
<console>:14: error: no type parameters for method traverseKTrampoline: (f: Int => scalaz.Kleisli[G,S,B])(implicit evidence$2: scalaz.Applicative[G])scalaz.Kleisli[G,S,List[B]] exist so that it can be applied to arguments (Int => scalaz.Kleisli[[+α]Int,Int,Int])
--- because ---
argument expression's type is not compatible with formal parameter type;
found : Int => scalaz.Kleisli[[+α]Int,Int,Int]
required: Int => scalaz.Kleisli[?G,?S,?B]
List(1, 2, 3) traverseKTrampoline { x => Monoidal { _: Int => x + 1 } }
^
Is this the infamous SI-2712? Then I thought, ok I’ll turn this into an actual type:
trait MonoidApplicative[F] extends Applicative[({type λ[α]=F})#λ] { self =>
implicit def M: Monoid[F]
def point[A](a: => A) = M.zero
def ap[A, B](fa: => F)(f: => F) = M.append(f, fa)
override def map[A, B](fa: F)(f: (A) => B) = fa
}
This does not work because now we have to convert x + 1 into MonoidApplicative.
Next I thought about giving Unapply a shot:
scala> List(1, 2, 3) traverseU {_ + 1}
<console>:14: error: Unable to unapply type `Int` into a type constructor of kind `M[_]` that is classified by the type class `scalaz.Applicative`
1) Check that the type class is defined by compiling `implicitly[scalaz.Applicative[<type constructor>]]`.
2) Review the implicits in object Unapply, which only cover common type 'shapes'
(implicit not found: scalaz.Unapply[scalaz.Applicative, Int])
List(1, 2, 3) traverseU {_ + 1}
^
This could work. All we have to do is unpack Int as ({type λ[α]=Int})#λ in Unapply:
trait Unapply_3 {
/** Unpack a value of type `A0` into type `[a]A0`, given a instance of `TC` */
implicit def unapplyA[TC[_[_]], A0](implicit TC0: TC[({type λ[α] = A0})#λ]): Unapply[TC, A0] {
type M[X] = A0
type A = A0
} = new Unapply[TC, A0] {
type M[X] = A0
type A = A0
def TC = TC0
def apply(ma: M[A0]) = ma
}
}
Let’s try:
scala> List(1, 2, 3) traverseU {_ + 1}
res0: Int = 9
This actually worked! Can we combine this?
scala> val f = { (x: Int) => x + 1 }
f: Int => Int = <function1>
scala> val g = { (x: Int) => List(x, 5) }
g: Int => List[Int] = <function1>
scala> val h = f &&& g
h: Int => (Int, List[Int]) = <function1>
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))
scala> List(1, 2, 3) traverseU h
res2: (Int, List[List[Int]]) = (9,List(List(1, 5), List(2, 5), List(3, 5)))
I am guessing either res1 or res2 is wrong. res1 is what traverse is supposed to return at least from what I checked in Haskell. Because Tuple2 is also an applicative it’s doing something unexpected. I was able to confirm this behavior without my changes, so let’s add a test:
"traverse int function as monoidal applicative" in {
val s: Int = List(1, 2, 3) traverseU {_ + 1}
s must be_===(9)
}
Let’s run it:
scalaz-tests> test-only scalaz.TraverseTest
[info] list should
[info] + apply effects in order
[info] + traverse through option effect
[info] + traverse int function as monoidal applicative
[info] + not blow the stack
[info] + state traverse agrees with regular traverse
[info] + state traverse does not blow stack
...
[success] Total time: 183 s, completed Sep 19, 2012 8:09:03 AM
Branch out from scalaz-seven and make topic/unapplya branch:
$ git co scalaz-seven
M core/src/main/scala/scalaz/Unapply.scala
M tests/src/test/scala/scalaz/TraverseTest.scala
Switched to branch 'scalaz-seven'
$ git branch topic/unapplya
$ git co topic/unapplya
M core/src/main/scala/scalaz/Unapply.scala
M tests/src/test/scala/scalaz/TraverseTest.scala
Switched to branch 'topic/unapplya'
If all the tests pass, I am committing this as “adds implicit def unapplyA, which unpacks A into [a]A.”
$ git push fork topic/unapplya
...
* [new branch] topic/unapplya -> topic/unapplya
Let’s send this as a pull request too. This was fun.
We’ll pick it up from here later.