Created
January 3, 2015 16:15
-
-
Save begeric/b28c02819cc70c530ed9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import scala.reflect.ClassTag | |
| trait AllowedTransfomation[I, O] | |
| trait ToType[A, B] | |
| trait Monoid[A]{ | |
| def zero : A | |
| def append(a: A, b: A): A | |
| } | |
| object Monoid { | |
| implicit object Void extends Monoid[Unit] { | |
| def zero = () | |
| def append(a: Unit, b: Unit) = () | |
| } | |
| } | |
| trait Traverser[T] { | |
| type MatchResult[+U <: T, A] = Option[(U, A)] | |
| implicit object obvious extends ToType[T, T] | |
| //implicit def obvious2[U] = new ToType[U, T]{} | |
| abstract class Matcher[+A] { self => | |
| def compose[B >: A : Monoid](m: => Matcher[B]) = new Matcher[B] { | |
| def apply[I <: T, O <: T](tree: I)(implicit x: ToType[I, O]) = { | |
| self.apply[I, O](tree).map { | |
| case t @ (a1 : O, a2) => m.apply[T,T](a1) //Error:(31, 35) could not find implicit value for parameter x: ToType[O,O] | |
| .map{case (b1 : O, b2) => (b1, implicitly[Monoid[B]].append(a2, b2))} | |
| .getOrElse(t) | |
| }.orElse(m.apply[I, O](tree)) | |
| } | |
| } | |
| def apply[I <: T, O <: T ](t: I)(implicit x: ToType[I, O]): MatchResult[O, A] | |
| } | |
| def traverse[I <: T, A : Monoid](tree: I, f: Matcher[A]) : MatchResult[I, A] | |
| } | |
| trait Combinators[T] { self: Traverser[T] => | |
| def children[A : Monoid](f: => Matcher[A]) = new Matcher[A]{ | |
| def apply[I <: T, O <: T](tree: I)(implicit x: ToType[I, O]) = traverse(tree, f).asInstanceOf[MatchResult[O, A]] | |
| } | |
| def down[A : Monoid](m: Matcher[A]): Matcher[A] = new Matcher[A]{ | |
| def apply[I <: T, O <: T](tree: I)(implicit x: ToType[I, O]) = | |
| (m compose children(down[A](m))).apply[I, O](tree) | |
| } | |
| def transform[U <: T : ClassTag, V <: T, A : Monoid](f: PartialFunction[U, (V, A)])(implicit x: AllowedTransfomation[U, V]) = new Matcher[A]{ | |
| def apply[I <: T, O <: T](tree: I)(implicit x: ToType[I, O]) = tree match { | |
| case t: U if f.isDefinedAt(t) => Some(f(t).asInstanceOf[(O, A)]) | |
| case _ => None | |
| } | |
| } | |
| } | |
| trait AST | |
| trait Term extends AST | |
| trait Stat extends AST | |
| case class Value(x: Int) extends Term | |
| case class If(cond: Term, thn: Term, els: Term) extends Term | |
| case class Block(stats: List[Term]) extends Term | |
| object ASTTraverser extends Traverser[AST] with Combinators[AST] { | |
| implicit object a1 extends ToType[Value, Term] | |
| implicit object a2 extends ToType[If, Term] | |
| implicit object a3 extends ToType[Block, Term] | |
| implicit object a4 extends ToType[Term, Term] | |
| //just allow everything for now but really AllowedTransfomation and ToType should be the same thing | |
| implicit def allowed[I, O] = new AllowedTransfomation[I, O] {} | |
| def traverse[I <: AST, A : Monoid](tree: I, f: Matcher[A]): MatchResult[I, A] = tree match { | |
| //here I have to use asInstanceOf. In real life we would rather require the data structure to be copiable.. | |
| case v @ Value(x) => Some((tree, implicitly[Monoid[A]].zero)) | |
| case If(cond, thn, els) => for { | |
| (a1, a2) <- f(cond) | |
| (b1, b2) <- f(thn) | |
| (c1, c2) <- f(els) | |
| } yield (If(a1, b1, c1).asInstanceOf[I], implicitly[Monoid[A]].append(a2, implicitly[Monoid[A]].append(b2, c2))) | |
| case Block(stats) => | |
| val (newStats, newResults) = (for { | |
| s <- stats | |
| (a1, a2) <- f(s) | |
| } yield (a1, a2)).unzip | |
| Some((Block(newStats).asInstanceOf[I], newResults.foldLeft(implicitly[Monoid[A]].zero)((acc, a) => implicitly[Monoid[A]].append(acc, a)))) | |
| } | |
| } | |
| object Test extends App { | |
| import ASTTraverser._ | |
| import Monoid._ | |
| println("yo") | |
| val test = Block(List( | |
| Value(10), | |
| If(Value(1), Value(2), Value(3)), | |
| Value(11) | |
| )) | |
| val times2 = down(transform[Value, Value, Unit]{case Value(x) => (Value(x * 2), Void)}) | |
| val hey: ASTTraverser.MatchResult[Term, Unit] = times2(test) | |
| println(hey) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment