// Part 2 about Regular Expression Matching+ −
//==========================================+ −
+ −
// copy over all code from re.scala+ −
+ −
// (2a) Complete the function iterT which needs to+ −
// be tail-recursive(!) and takes an integer n, a + −
// function f and an x as arguments. This function + −
// should iterate f n-times starting with the + −
// argument x.+ −
+ −
import scala.annotation.tailrec+ −
+ −
@tailrec+ −
def iterT[A](n: Int, f: A => A, x: A): A = ...+ −
+ −
+ −
+ −
// (2b) Complete the size function for regular+ −
// expressions + −
+ −
def size(r: Rexp): Int = ...+ −
+ −
// two testcases about the sizes of simplified and + −
// un-simplified derivatives+ −
+ −
//val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))+ −
//size(iterT(20, (r: Rexp) => der('a', r), EVIL)) // should produce 7340068+ −
//size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) // should produce 8+ −
+ −
+ −
+ −
// (2c) Complete the fixpoint function below.+ −
+ −
@tailrec+ −
def fixpT[A](f: A => A, x: A): A = ...+ −
+ −
+ −
/* testcases+ −
+ −
//the Collatz function from CW 6 defined as fixpoint+ −
+ −
def ctest(n: Long): Long =+ −
if (n == 1) 1 else+ −
if (n % 2 == 0) n / 2 else 3 * n + 1+ −
+ −
// should all produce 1 + −
fixpT(ctest, 97L)+ −
fixpT(ctest, 871L)+ −
fixpT(ctest, 77031L)+ −
+ −
*/+ −
+ −
/*+ −
// the same function on strings using the regular expression+ −
// matcher+ −
+ −
def foo(s: String): String = {+ −
if (matcher("a", s)) "a" else+ −
if (matcher("aa" ~ STAR("aa"), s)) s.take(s.length / 2) + −
else "a" ++ s * 3+ −
}+ −
+ −
// should all produce "a" + −
fixpT(foo, "a" * 97)+ −
fixpT(foo, "a" * 871)+ −
+ −
*/+ −