package test.arr;
/**
This code is in the public domain.
@author Ross Judson
*/
object Test {
import arrow.Arrow._
import arrow._
def main(args: Array[String]): Unit = {
import Console.{println => p}
val m = arr {y: Int => y + 5} >>> {z: Int => z * 2};
val fiver = arr {z: Int => z + 5}
val n = fiver >>> (arr[Int,Double](i => i * 2.0))
val o = arr {z: Int => z + 4} >>> {x: Int => x * 2.0}
val s1 = Array(1,3,5,6,8,9)
val s2 = Array(3,5,2,1,9,5)
p(for (val Pair(a,b) <- s1.zip(s2)) yield a + b)
val adder = arr { p: Pair[Int,Int] => p._1 + p._2 } >>> print("valp add:")
val splitter = (arr { p: Pair[Int,Int] => p._1 + p._2 } &&& arr { p => p._1 - p._2 }) >>> print("split:")
p("Splitter: " + splitter)
val glue = arr { p: Pair[String, Int] => p._1 + " glue " + (p._2 / 2) }
val g2 = filter[Pair[String,Int],String] { case Pair(s, i) if (i % 2 == 0) => s + " glue even " + (i / 2) }
val display = arr { i: Int => Pair("" + i, i) }
s1 &&& display >>> g2 >>> printer
Pair(s1,s2) &&& splitter
s1 >>> {i: Int => i * 2} >>> printer
val ifOdd = arr{n: Int => n % 2 == 0}
type EitherStringNumber = Either[String,Double]
p(Array.range(0,8) &&& either( ifOdd, "Even", arr {k: Int => k / 3.3}))
p(o(m(12)))
}
}
Here's the implementation of Arrows:
package arrow;
/** Object Arrow supplies functions and implicit definitions
that provide a convenient environment for manipulating arrow
computations in a typesafe manner.
@author Ross Judson
Arrows are functions from one type to another, enriched with
additional operations that allow for composition and manipulation.
Such structures are problematic to encode in
many functional languages, but are quite straightforward to
deal with in Scala due to its dual functional and object
orientated nature. A function in Scala is an object that
exhibits a Function trait:
class AddTwo extends Function1[Int,Int] {
def apply(x: Int) = x + 2
}
In order to fulfill the Function1 trait, our object must
define the apply method. There are eight other
Function traits named for the number of arguments they
take (Function2 though Function8).
Arrows are computations from one type to another. We capture
the operations we want our arrow types to be able to handle
in the Arrow[I,O] trait, which extends the Function1[I,O]
trait. This makes every arrow into a full-fledged function
in the Scala language, and also makes it quite easy for us
to turn any function into an arrow.
The various arrow operations then become relatively simple
to implement, as we provide a simple way to lift regular
functions "up" into the arrow class (through a number of
mechanisms), and make use of a base class to provide
implementations of the operations. If a more efficient
implementation of an arrow operation can be written for a given
arrow type, we can supply it and rely on conventional late
binding to execute it.
Some of the functions use anonymous classes to produce arrows,
and those might be better placed in real classes instead. The
anonymous syntax is quite pure and keeps the focus on the algorithms,
but concrete class definitions might be easier to manipulate
during program design, when arrows are being combined together
into more complex computations. It is also somewhat more
efficient to have the class, as a "wrapper on wrapper" effect
is avoided.
*/
object Arrow {
/** Create a constant arrow, which is an arrow that always returns
a known value each time it is called, regardless of the input. */
implicit def const[I,O](v: O): Arrow[I,O] = new ConstArrow[I,O](v)
/** Lift a normal function to an arrow, which is enriched with a
large set of additional operations. */
implicit def arr[I,O](f: I => O): Arrow[I,O] = new PureArrow(f)
/** Create an identity arrow for a type. The identity arrow always
returns the input. */
def identity[I] = new IdentityArrow[I]
// Can't decide yet which one of these is more efficient. Probably
// the "longer" one, because there's there's no additional anonymous
// function being created and wrapped. On the other hand, who cares.
// def first[I,O,X](a: Arrow[I,O]) = arr { p: Pair[I,X] => a(p._1) }
/** First is one of the canonical arrow operations. Papers and
writings on arrow give definitions for many operations in terms
of the first operation. */
def first[I,O,X](a: Arrow[I,O]) = new AbstractArrow[Pair[I,X],O] {
def arrowtype = "First"
def apply(p: Pair[I,X]) = a(p._1)
}
/** Create an arrow that pairs up the output of two other arrows. */
def zip[I,O,P](a: Arrow[I,O], b: Arrow[I,P]) = arr { i:I => Pair(a(i),b(i)) }
/** Create an arrow that duplicates its input into pairs. */
implicit def dup[I] = arr { i: I => Pair(i,i) }
/** Creates an arrow that emits an Option based on the given
partial function. This is convenient when used in conjunction
with Scala's anonymous partial functional syntax. */
def filter[I,O](f: PartialFunction[I,O]): Arrow[I, Option[O]] =
arr {i: I => if (f.isDefinedAt(i)) Some(f(i)) else None}
/** Creates an arrow on a binary function that receives pairs as
the input, then invokes the binary function with the items in the
pair. The result of the arrow is the result of the function. */
implicit def pairing[A,B,C](f: (A,B) => C): Arrow[Pair[A,B],C] = arr { p => f(p._1, p._2) }
/** Lift an arrow so that it can operate against a stream. */
def streamArr[I,O](a: Arrow[I,O]) = arr { is: Stream[I] => is.map(a) }
/** Lift an arrow so it can operate against a list. */
def listArr[I,O](a: Arrow[I,O]) = arr { il: List[I] => il.map(a) }
/** Lift an arrow so it can operate against an array. */
def arrayArr[I,O](a: Arrow[I,O]) = arr { il: Array[I] => il.map(a) }
/** Prints whatever comes though on a line. Keeps going. */
def printer[I] = arr { i: I => { Console.println(i); i } }
/** Prints whatever comes though it, prepending a message. */
def print[I](msg: String) = arr { i: I => { Console.print(msg); Console.println(i); i }}
/** Raises a Stream to a SupplyStream, which can push its contents
through an arrow. This creates the illusion that additional methods
are available on arrays (following the pattern used by the "Rich" family
of classes in Scala's standard library. */
implicit def streamSupply[I](s: Stream[I]) = new SupplyStream(s)
/** Raises an array to a SupplyArray, which can push its contents
though an arrow. */
implicit def arraySupply[I](a: Array[I]) = new SupplyArray(a)
/** Create an arrow that uses the first arrow is a selector to
decide if the input value should be routed to the second or the
third arrow. The result is an Either type, so further usages
can be pattern-matched on precise types with GADTs. */
def either[I,A,B](sel: Arrow[I,Boolean], a: Arrow[I,A], b: Arrow[I,B]) =
arr { i: I => if (sel(i)) Left(a(i)) else Right(b(i)) }
private type PA[A,B] = Pair[Array[A], Array[B]]
private type PS[A,B] = Pair[Stream[A], Stream[B]]
implicit def pairArraySupply[A,B,C](ps: PA[A,B]) = new PairedSupplyArray(ps._1, ps._2)
implicit def pairStreamSupply[A,B,C](ps: PS[A,B]) = new PairedSupplyStream(ps._1, ps._2)
}
/** An Arrow is a function from I to O, enriched with
additional functions for composition. */
trait Arrow[I,O] extends Function1[I,O] {
/** Combine this arrow (from I to O) with another arrow
from O to X, creating a single arrow from I to X. */
def compose[X](a: Arrow[O, X]): Arrow[I,X];
/** An operator synonym for the compose method. */
def >>>[X](a: Arrow[O, X]): Arrow[I,X];
/** Combines this arrow with another that takes the
same type of input to create an arrow that creates a
pair of the outputs of this arrow and the other. */
def par[X](b: Arrow[I,X]): Arrow[I,Pair[O,X]];
/** An operator synonym for the par method. */
def &&&[X](b: Arrow[I,X]): Arrow[I,Pair[O,X]];
def intype: String
def outtype: String
def arrowtype: String
}
/** RichArrow is a trait that provides implementations for
some of the methods in the Arrow interface. It can be used
as a mixin to create new arrow types. If possible it's a
good idea to inherit from abstract arrow to avoid the mixin
space penalty. */
trait RichArrow[I,O] extends Arrow[I,O] {
def >>>[X](a: Arrow[O, X]) = compose(a)
def compose[X](a: Arrow[O, X]): Arrow[I,X] = new ComposeArrow(this, a)
def &&&[X](b: Arrow[I,X]) = par(b)
def par[X](b: Arrow[I,X]) = Arrow.zip(this,b)
def intype = "?"
def outtype = "?"
override def toString = arrowtype + '(' + intype + "-->" + outtype + ')'
}
abstract class AbstractArrow[I,O] extends RichArrow[I,O];
class ConstArrow[I,O](v: O) extends AbstractArrow[I,O] {
def apply(i: I) = v
def arrowtype = "Const"
override def toString = "Const(" + intype + "-->" + v.toString + ')'
}
class PureArrow[I,O](f: I => O) extends AbstractArrow[I,O] {
def apply(i: I) = f(i)
def arrowtype = "Pure"
override def toString = "Pure(" + intype + "-->" + outtype + ')'
}
private class TypedPureArrow[I,O](f: I => O, in: String, out: String) extends PureArrow(f) {
override def intype = in
override def outtype = out
}
class IdentityArrow[I] extends AbstractArrow[I,I] {
def apply(i: I) = i
def arrowtype = "Identity"
/** If we compose the identity arrow with another arrow
we can just use the other arrow, as this one has no effect. */
override def compose[X](a: Arrow[I, X]) = a
}
/** SinkList is an identity arrow that collects what's
passing through it into a list, which can be retrieved
by toList. */
class SinkList[I] extends AbstractArrow[I,I] {
def arrowtype = "SinkList"
private var lst = List[I]()
/** Executes sink, saving the operand then returning it. */
def apply(i: I) = { lst = i :: lst; i }
}
/** An arrow class that represents the composition of one arrow with
another. We break this out rather than use anonymous classes so it
is easier to see the structure of arrows in a system. */
class ComposeArrow[I,O,X](a1: Arrow[I,O], a2: Arrow[O,X]) extends AbstractArrow[I,X] {
def arrowtype = "Compose"
override def toString = arrowtype + '(' + a1 + "-->" + a2 + ')'
override def intype = a1.intype
override def outtype = a2.outtype
def apply(i: I) = a2(a1(i))
}
class SupplyStream[I](s: Stream[I]) {
def supply[O](a: Arrow[I,O]) = s.map(a)
def &&&[O](a: Arrow[I,O]) = supply(a)
}
class SupplyArray[I](s: Array[I]) {
def supply[O](a: Arrow[I,O]) = s.map(a)
def &&&[O](a: Arrow[I,O]) = supply(a)
}
class PairedSupplyArray[A,B](a: Array[A], b: Array[B]) {
def supply[O](f: Arrow[Pair[A,B],O]) = a.zip(b).map(f)
def &&&[O](f: Arrow[Pair[A,B],O]) = supply(f)
}
class PairedSupplyStream[A,B](a: Stream[A], b: Stream[B]) {
def supply[O](f: Arrow[Pair[A,B],O]) = a.zip(b).map(f)
def &&&[O](f: Arrow[Pair[A,B],O]) = supply(f)
}
trait MustExist;
sealed trait Either[L,R];
case object Neither extends Either[Nothing,Nothing];
trait EitherMustExist[L,R] extends Either[L,R] with MustExist;
case class Left[L,R](value: L) extends EitherMustExist[L,R]
case class Right[L,R](value: R) extends EitherMustExist[L,R];
sealed trait Choose3[A,B,C];
trait Choose3MustExist[A,B,C] extends Choose3[A,B,C] with MustExist;
case object NoChoice extends Choose3[Nothing,Nothing,Nothing];
case class First[A,B,C](value: A) extends Choose3MustExist[A,B,C];
case class Second[A,B,C](value: B) extends Choose3MustExist[A,B,C];
case class Third[A,B,C](value: C) extends Choose3MustExist[A,B,C];