# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1480000002 0
# Node ID 9d8b172f5337f5817cb71d0aac1d6f6359df5448
# Parent  19dff7218b0d972ec0bce62205eceb7b15336892
updated

diff -r 19dff7218b0d -r 9d8b172f5337 progs/lecture3.scala
--- a/progs/lecture3.scala	Thu Nov 24 11:43:07 2016 +0000
+++ b/progs/lecture3.scala	Thu Nov 24 15:06:42 2016 +0000
@@ -37,18 +37,20 @@
 
 
 //factorial V0.1
+import scala.annotation.tailrec
+
 
 def fact(n: Long): Long = 
   if (n == 0) 1 else n * fact(n - 1)
 
 fact(10000)                        // produces a stackoverflow
 
-
+@tailrec
 def factT(n: BigInt, acc: BigInt): BigInt =
   if (n == 0) acc else factT(n - 1, n * acc)
 
 
-factT(10000, 1)
+println(factT(10000, 1))
 
 // the functions my_contains and factT are tail-recursive 
 // you can check this with 
@@ -80,6 +82,8 @@
 }
 
 
+import scala.annotation.tailrec
+
 def search(total: Int, coins: List[Int], cs: List[Int]): Option[List[Int]] = {
   if (total < cs.sum) None 
   else if (cs.sum == total) Some(cs) 
@@ -98,7 +102,8 @@
 import scala.annotation.tailrec
 
 @tailrec
-def searchT(total: Int, coins: List[Int], acc_cs: List[List[Int]]): Option[List[Int]] = acc_cs match {
+def searchT(total: Int, coins: List[Int], 
+            acc_cs: List[List[Int]]): Option[List[Int]] = acc_cs match {
   case Nil => None
   case x::xs => 
     if (total < x.sum) searchT(total, coins, xs)
@@ -119,16 +124,16 @@
 // Polymorphic Types
 //===================
 
-// You do not want to frite functions like contains, first 
+// You do not want to write functions like contains, first 
 // and so on for every type of lists.
 
 
-def length_int_list(lst: List[Int]): Int = lst match {
+def length_string_list(lst: List[String]): Int = lst match {
   case Nil => 0
-  case x::xs => 1 + length_int_list(xs)
+  case x::xs => 1 + length_string_list(xs)
 }
 
-length_int_list(List(1, 2, 3, 4))
+length_string_list(List("1", "2", "3", "4"))
 
 
 def length[A](lst: List[A]): Int = lst match {
@@ -156,6 +161,8 @@
 case class Node[A](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A]
 case object Leaf extends Tree[Nothing]
 
+val t0 = Node('4', Node('2', Leaf, Leaf), Node('7', Leaf, Leaf))
+
 def insert[A](tr: Tree[A], n: A): Tree[A] = tr match {
   case Leaf => Node(n, Leaf, Leaf)
   case Node(m, left, right) => 
@@ -168,7 +175,8 @@
 // the A-type needs to be ordered
 
 abstract class Tree[+A <% Ordered[A]]
-case class Node[A <% Ordered[A]](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A]
+case class Node[A <% Ordered[A]](elem: A, left: Tree[A], 
+                                 right: Tree[A]) extends Tree[A]
 case object Leaf extends Tree[Nothing]
 
 
@@ -198,12 +206,12 @@
 case object ONE extends Rexp
 case class CHAR(c: Char) extends Rexp
 case class ALT(r1: Rexp, r2: Rexp) extends Rexp     // alternative  r1 + r2
-case class SEQ(r1: Rexp, r2: Rexp) extends Rexp     // sequence     r1 r2    
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp     // sequence     r1 r2  
 case class STAR(r: Rexp) extends Rexp               // star         r*
 
 
 // (ab)*
-val r0 = ??
+val r0 = STAR(SEQ(CHAR('a'), CHAR('b')))
 
 
 // some convenience for typing in regular expressions
@@ -220,8 +228,7 @@
 
 val r1 = STAR("ab")
 val r2 = STAR("")
-val r3 = STAR(ALT("ab", "ba"))
-
+val r3 = STAR(ALT("ab", "baa baa black sheep"))
 
 implicit def RexpOps (r: Rexp) = new {
   def | (s: Rexp) = ALT(r, s)
@@ -259,7 +266,7 @@
 
 def expensiveOperation(n: BigInt): Boolean = expensiveOperation(n + 1) 
 val a = "foo"
-val b = "foo"
+val b = "bar"
 
 val test = if ((a == b) || expensiveOperation(0)) true else false