progs/re2.scala
changeset 78 85f2f75abeeb
parent 68 8da9e0c16194
equal deleted inserted replaced
75:71e463b33a9e 78:85f2f75abeeb
       
     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 */