λ Tony's blog λ

The weblog of Tony Morris

Posted on January 25, 2009, in Programming

I decided to play around with arrows and Scala to see how far I could get. I remember vividly the effort required to get a Monad abstraction for Scalaz to work and be useful all at once with so many competing tensions (e.g. type inferencer, composability, repetition).

I didn’t go so far as to test the usefulness, but I was able to express the Kleisli arrow without too much effort. I wonder if it is a viable addition for Scalaz.

Here it is.

The typical Functor/Monad abstraction. These are required for the Kleisli arrow.

```
trait Functor[F[+_]] {
def fmap[A, B](fa: F[A], f: A => B): F[B]
}
trait Monad[M[+_]] extends Functor[M] {
def pure[A](a: A): M[A]
def bind[A, B](ma: M[A], f: A => M[B]): M[B]
final def fmap[A, B](fa: M[A], f: A => B) =
bind(fa, (a: A) => pure(f(a)))
}
```

The Kleisli data type and a convenient constructor.

```
trait Kleisli[M[+_], -A, +B] {
def apply(a: A): M[B]
}
object Kleisli {
def kleisli[M[+_], A, B](f: A => M[B]) = new Kleisli[M, A, B] {
def apply(a: A) = f(a)
}
}
```

The arrow abstraction.

```
trait Arrow[A[-_, +_]] {
def arrow[B, C](f: B => C): A[B, C]
def compose[B, C, D](a1: A[B, C], a2: A[C, D]): A[B, D]
def first[B, C, D](a: A[B, C]): A[(B, D), (C, D)]
def second[B, C, D](a: A[B, C]): A[(D, B), (D, C)]
}
```

and the clincher…

```
object Arrow {
val Function1Arrow = new Arrow[Function1] {
def arrow[B, C](f: B => C) = f
def compose[B, C, D](a1: B => C, a2: C => D) =
a2 compose a1
def first[B, C, D](a: B => C) =
(bd: (B, D)) => (a(bd._1), bd._2)
def second[B, C, D](a: B => C) =
(db: (D, B)) => (db._1, a(db._2))
}
def KleisliArrow[M[+_]](implicit m: Monad[M]) =
new Arrow[PartialType[Kleisli, M]#Apply] {
import Kleisli.kleisli
def arrow[B, C](f: B => C) =
kleisli[M, B, C](b => m.pure(f(b)))
def compose[B, C, D](a1: Kleisli[M, B, C], a2: Kleisli[M, C, D]) =
kleisli[M, B, D](b => m.bind(a1(b), (c: C) => a2(c)))
def first[B, C, D](a: Kleisli[M, B, C]) =
kleisli[M, (B, D), (C, D)] { case (b, d) => m.fmap(a(b), (c: C) => (c, d)) }
def second[B, C, D](a: Kleisli[M, B, C]) =
kleisli[M, (D, B), (D, C)]{ case (d, b) => m.fmap(a(b), (c: C) => (d, c)) }
}
}
```

TODO

Write functions across arrows.

Can arrows be made useful within the constraints of Scala?