Zajęcia nr 3

• Slajdy do wykładu
• Wykonać ćwiczenia do omówionego materiału z podręcznika.

Ćwiczenia

1. Exercise 9.1.1 Provide an implementation of the missing function insert.

   def isort(xs: List[Int]): List[Int] =
     if (xs.isEmpty) Nil
     else insert(xs.head, isort(xs.tail))
   

2. Exercise 9.2.1 Design a tail-recursive version of length.
3. Exercise 9.4.1 Consider a function which squares all elements of a list and re- turns a list with the results. Complete the following two equivalent definitions of squareList.

   def squareList(xs: List[Int]): List[Int] = xs match {
     case List() => ??
     case y :: ys => ??
   }
   
   def squareList(xs: List[Int]): List[Int] =
     xs map ??
   

4. Exercise: Define forall and exists in terms of filter.
5. Exercise 9.4.3 Fill in the missing expressions to complete the following definitions of some basic list-manipulation operations as fold operations.

   def mapFun[A, B](xs: List[A], f: A => B): List[B] =
     (xs :\ List[B]()){ ?? }
   
   def lengthFun[A](xs: List[A]): int =
     (0 /: xs){ ?? }
   

Rozwiązania

1. def isort(xs: List[Int]): List[Int] =
     if (xs.isEmpty) Nil
     else insert(xs.head, isort(xs.tail))
   
   def insert(x: Int, xs: List[Int]): List[Int] =
     if (xs.isEmpty) List(x)
     else if (x < xs.head) x::xs
     else xs.head :: insert(x, xs.tail)
   

2. def len(l: List[Any]):Int = {
     def len_pom(n: Int, lpom: List[Any]):Int = {
       if (lpom.isEmpty) n
       else len_pom(n+1, lpom.tail)
     }
     len_pom(0,l)
   }
   

3. def squareList(xs: List[Int]): List[Int] = xs match {
     case List() => xs
     case y :: ys => y*y :: squareList(ys)
   }
   
   def squareList2(xs: List[Int]): List[Int] =
     xs map (x=>x*x)
   

4. def forall[T](list: List[T], condition: T => Boolean) =
      (list filter (x => !condition(x))) == Nil
   
    def exists[T](list: List[T], condition: T => Boolean) =
      (list filter (x => condition(x))) != Nil
   

5. def mapFun[A, B](xs: List[A], f: A => B): List[B] =
     (xs :\ List[B]()){ (item,list) => f(item)::list }
   
   def lengthFun[A](xs: List[A]): int =
     (0 /: xs){ ((len,item) => len+1) }