MI-PSL-8

Question 1

What are main features of collection List?

Answer 1

List je základní datovou strukturou funkcionálního programování. Jejich hlavní výhody:

jsou immutable
mají rekurzivní strukturu
je předdefinováno velké množství funkcí pro práci s listy

Question 2

Do write the definition of the class which defines the node of the list.

Answer 2

final case class ::B extends List[B] {def isEmpty = false}

Question 3

Do write the definition of Nil.

Answer 3

case object Nil extends List[Nothing] {
override def isEmpty = true
override def head: Nothing =
throw new NoSuchElementException(“empty list”)
override def tail: List[Nothing] =
throw new UnsupportedOperationException
(“empty list”)

Question 4

Do write the concatenation function of the class List.

Answer 4

def ::[B >: A] (x: B): List[B] =
   new scala.collection.immutable.::(x, this)

Question 5

What are the elementary operations of list by which the other can be defined.

Answer 5

funkce:

head - vrací první prvek listu
tail - vrací zbytek listu
isEmpty - indikuje zda je seznam prázdný

Question 6

Write the definition of method List.length

Answer 6

def length: Int = this match {
     case Nil => 0
     case x :: xs => 1 + xs.length
   }

Question 7

Write the definition of method List.init

Answer 7

def init: A = this match {
   case Nil => error("Nil.last")
   case x :: Nil => Nil
   case x :: xs => x :: xs.init
 }

Question 8

Write the definition of method List.last

Answer 8

def last: A = this match {
   case Nil => error("Nil.last")
   case x :: Nil => x
   case x :: xs => xs.last
 }

Question 9

Write the definition of method List.take

Answer 9

def take(n: Int): List[A] =
if (n == 0 || isEmpty) Nil
else head :: tail.take(n-1)

Question 10

Write the definition of method List.drop

Answer 10

def drop(n: Int): List[A] =
if (n == 0 || isEmpty) this
else tail.drop(n-1)

Question 11

Write the method which enables list subscripting.

Answer 11

def apply(n: Int): A = drop(n).head

Question 12

Write the method which enables list concatenation.

Answer 12

def :::[B >: A](prefix: List[B]): List[B] =
    prefix match {
      case Nil => this
      case x :: xs => this.:::(xs).::(x)
  }

Question 13

Write the definition of method List.map

Answer 13

def map[B](f: A => B): List[B] =
      this match {
        case Nil => this
        case x :: xs => f(x) :: xs.map(f)
      }

Question 14

Write the definition of method List.foreach

Answer 14

def foreach(f: A => Unit) {
    this match {
      case Nil => ()
      case x :: xs => f(x); xs.foreach(f)
    }   
  }

Question 15

Write the definition of method List.filter

Answer 15

def filter(p: A => Boolean): List[A] = 
    this match {
      case Nil => this
      case x :: xs =>
                if (p(x)) x :: xs.filter(p)
                else xs.filter(p)
  }

Question 16

Describe reduceLeft.

Answer 16

Kombinuje prvky listu nějakým operátorem. Např pro list 1 2 3 4 5 a operaci + udělá následující: ((((1 + 2) + 3) + 4) + 5). Př.

def sum(xs: List[Int]) = // xs != Nil
    xs reduceLeft {(x, y) => x + y}

Question 17

Describe foldLeft

Answer 17

Metoda reduceLeft selže na prázdném listu. Toto řeší metoda foldLeft, které se jako argument předává neutrální prvek dané operace. Pro + je to 0, pro * je to 1. Př.

def sum(xs: List[Int]) =
    (xs foldLeft 0) { (x, y) => x + y }

Question 18

Describe flatMap

Answer 18

Metoda flatMap aplikuje nějakou funkci f na všechny prvky seznamu a výsledné podlisty zřetězí