Last active
August 29, 2015 14:12
-
-
Save begeric/d4362897030487ec9aef 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)] | |
| abstract class Matcher[+A] { | |
| def compose[B >: A : Monoid](m: => Matcher[B]) = new Matcher[B] { | |
| def apply[I <: T, O <: T](tree: I)(implicit x: ToType[I, O]) = { | |
| this(tree).map { | |
| case t @ (a1, a2) => m(a1) //Error:(31, 35) could not find implicit value for parameter x: ToType[O,O] | |
| .map{case (b1, b2) => (b1, implicitly[Monoid[B]].append(a2, b2))} | |
| .getOrElse(t) | |
| }.orElse(m(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 >: I <: T](tree: I)(implicit x: ToType[I, O]) = traverse(tree, f) | |
| } | |
| 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 <: U, O >: V](tree: I)(implicit x: ToType[I, O]) = tree match { | |
| case t: U => Some(f(t)) | |
| 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] | |
| 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 Value(x) => Some((Value(x).asInstanceOf[I], 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 Hey extends App { | |
| println("yo") | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment