Lab nr 1

Ćwiczenia

1. Napisz wersję poniższej funkcji sum z rekursją ogonową zamiast rekursji liniowej przez uzupełnienie miejsc oznaczonych ??

   def sum(f: Int => Double)(a: Int, b: Int): Double = {
     def iter(a, result) = {
       if (??) ??
       else iter(??, ??)
     }
     iter(??, ??)
   }
   

2. Napisz funkcję product, która oblicza iloczyn wartości zadanej funkcji w punktach z podanego zakresu.
3. Przy pomocy rozwiązania poprzedniego zadania zdefiniuj silnię.
4. Napisz funkcję, która uogólnia zarówno produkt jak i sumę (najlepiej z rekrusją ogonową).
5. Przy pomocy fixedPoint oraz averageDamp napisz funkcję liczącą pierwiastek trzeciego stopnia.
6. Napisz metody union oraz intersection znajdujące sumę i przecięcie dwóch zbiorów.
7. Zaimplementuj metodę def excl(x: Int), która zwraca zbiór po usunięciu z niego wskazanego elementu x.
8. Zaimplementuj klasę Integer reprezentującą liczby całkowite. Implementcja powinna wspierać wszystkie operacje z klasy class Nat oraz dodawać dwie metody

   def isPositive: Boolean
   def negate: Integer
   

   Nie używaj żadnych standardowych klas numerycznych z Scali (rozszerz Nat o znak lub dodaj do hierarchii Nat nową podklasę Pred dla liczby ujemnych).
9. Poniższa implementacja drzewa liczb całkowitych może być traktowana jako alternatywna reprezentacja IntSet:

   abstract class IntTree
   case object EmptyTree extends IntTree
   case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
   

   Uzupełnij poniższe implementacje funkcji z klasy IntTree.

   def contains(t: IntTree, v: Int): Boolean = t match { ...
     ...
   }
   
   def insert(t: IntTree, v: Int): IntTree = t match { ...
     ...
   }
   

Rozwiązania

1. def sum(f: Int => Double)(a: Int, b: Int): Double = {
     def iter(a: Int, result:Double):Double = {
       if (a>b) result
       else iter(a+1, result+f(a))
     }
     iter(a, 0)
   }
   

2. def oper_iter(oper: (Double,Double)=>Double)(f: Int => Double)(a: Int, b: Int): Double = {
     def iter(a: Int, result:Double):Double = {
       if (a>b) result
       else iter(a+1, oper(result,f(a)))
     }
     iter(a+1, f(a))
   }
   
   def product(f: Int => Double)(a: Int, b: Int): Double = oper_iter((x,y) => x*y)(f)(a,b)
   def sum(f: Int => Double)(a: Int, b: Int): Double = oper_iter((x,y) => x+y)(f)(a,b)
         
   def factorial(n:Int) = product(x=>x) (1,n)
            
   def main(args: Array[String]) = {
     println(sum(x=>x)(1,2))
     println(factorial(4))
   }
   

3. j.w.
4. j.w.

5. val tolerance = 0.0001
   def isCloseEnough(x: Double, y: Double) = Math.abs((x - y) / x) < tolerance
   
   def fixedPoint(f: Double => Double)(firstGuess: Double) = {
     def iterate(guess: Double): Double = {
       val next = f(guess)
       if (isCloseEnough(guess, next)) next
       else iterate(next)
     }
     iterate(firstGuess)
   }
   
   def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2
   
   def sqrt(x: Double) = fixedPoint(averageDamp(y => x/y))(1.0)
   
   def cuberoot(x: Double) = fixedPoint(averageDamp(y => x/( Math.pow(y,2) )))(1.0)
   
   def main(args: Array[String]) = {
     println( sqrt(2.0) );
     println( cuberoot(2.0) );
   }
   

6. trait IntSet {
     def incl(x: Int): IntSet
     def contains(x: Int): Boolean
     def union(s: IntSet): IntSet
     def intersection(s: IntSet): IntSet
     def foreach(f: Int => Unit)
     def excl(x:Int): IntSet
   }
   
   class EmptySet extends IntSet {
     def contains(x: Int): Boolean = false
     def incl(x: Int): IntSet = new NonEmptySet(x, new EmptySet, new EmptySet)
     def union(s: IntSet): IntSet = s
     def intersection(s: IntSet): IntSet = this
     def foreach(f: Int => Unit) = {}
     def excl(x:Int): IntSet = this
   }
   
   class NonEmptySet(elem: Int, left: IntSet, right: IntSet) extends IntSet {
     def contains(x: Int): Boolean =
       if (x < elem) left contains x
       else if (x > elem) right contains x
       else true
   
     def incl(x: Int): IntSet =
       if (x < elem) new NonEmptySet(elem, left incl x, right)
       else if (x > elem) new NonEmptySet(elem, left, right incl x)
       else this
   
     def union(s: IntSet): IntSet =
       right.union(left.union(s.incl(elem)))
     
     def intersection(s: IntSet): IntSet =
       {
         val le = left.intersection(s)
         val ri = right.intersection(s)
         val ret = le.union(ri)
         if (s.contains(elem))
           new NonEmptySet(elem, le, ri)
         else
           le.union(ri)
       }
   
     def foreach(f: Int => Unit) =
       {
         left.foreach(f)
         f(this.elem)
         right.foreach(f)
       }
   
     def excl(x:Int): IntSet =
       if (x < elem) new NonEmptySet(elem, left excl x, right)
       else if (x > elem) new NonEmptySet(elem, left, right excl x)
       else left.union(right)
   }
   
   

7. j.w.

8. TODO
   

9. abstract class IntTree
   case object EmptyTree extends IntTree
   case class Node(elem: Int, left: IntTree, right: IntTree) extends IntTree
   
   def contains(t: IntTree, x: Int): Boolean = t match
   {
     case EmptyTree => false
     case Node(elem, left, right) =>
       if (x < elem) contains (left, x)
       else if (x > elem) contains (right, x)
       else true
   }
   
   def insert(t: IntTree, x: Int): IntTree = t match
   {
     case EmptyTree => new Node(x, EmptyTree, EmptyTree)
     case Node(elem, left, right) =>
       if (x < elem) new Node(x, insert(left,x), right)
       else if (x > elem) new Node(x, left, insert(right,x))
       else t
   }