|
1 // Part 2 about Regular Expression Matching |
|
2 //========================================== |
|
3 |
|
4 // copy over all code from re.scala |
|
5 |
|
6 // (2a) Complete the function iterT which needs to |
|
7 // be tail-recursive(!) and takes an integer n, a |
|
8 // function f and an x as arguments. This function |
|
9 // should iterate f n-times starting with the |
|
10 // argument x. |
|
11 |
|
12 import scala.annotation.tailrec |
|
13 |
|
14 @tailrec |
|
15 def iterT[A](n: Int, f: A => A, x: A): A = ... |
|
16 |
|
17 |
|
18 |
|
19 // (2b) Complete the size function for regular |
|
20 // expressions |
|
21 |
|
22 def size(r: Rexp): Int = ... |
|
23 |
|
24 // two testcases about the sizes of simplified and |
|
25 // un-simplified derivatives |
|
26 |
|
27 //val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b')) |
|
28 //size(iterT(20, (r: Rexp) => der('a', r), EVIL)) // should produce 7340068 |
|
29 //size(iterT(20, (r: Rexp) => simp(der('a', r)), EVIL)) // should produce 8 |
|
30 |
|
31 |
|
32 |
|
33 // (2c) Complete the fixpoint function below. |
|
34 |
|
35 @tailrec |
|
36 def fixpT[A](f: A => A, x: A): A = ... |
|
37 |
|
38 |
|
39 /* testcases |
|
40 |
|
41 //the Collatz function from CW 6 defined as fixpoint |
|
42 |
|
43 def ctest(n: Long): Long = |
|
44 if (n == 1) 1 else |
|
45 if (n % 2 == 0) n / 2 else 3 * n + 1 |
|
46 |
|
47 // should all produce 1 |
|
48 fixpT(ctest, 97L) |
|
49 fixpT(ctest, 871L) |
|
50 fixpT(ctest, 77031L) |
|
51 |
|
52 */ |
|
53 |
|
54 /* |
|
55 // the same function on strings using the regular expression |
|
56 // matcher |
|
57 |
|
58 def foo(s: String): String = { |
|
59 if (matcher("a", s)) "a" else |
|
60 if (matcher("aa" ~ STAR("aa"), s)) s.take(s.length / 2) |
|
61 else "a" ++ s * 3 |
|
62 } |
|
63 |
|
64 // should all produce "a" |
|
65 fixpT(foo, "a" * 97) |
|
66 fixpT(foo, "a" * 871) |
|
67 |
|
68 */ |