Zajęcia nr 5

Ćwiczenia

  1. Exercise 10.1.1 Write the function 
    def isSafe(col: Int, row: Int, queens: List[Int]): Boolean
  2. Exercise 10.3.1 Define the following function in terms of for. 
      def flatten[A](xss: List[List[A]]): List[A] =
    (xss :\ (Nil: List[A])) ((xs, ys) => xs ::: ys)
  3. Exercise 10.3.2 Translate 
      for (b <- books; a <- b.authors if a startsWith "Bird") yield b.title
  for (b <- books if (b.title indexOf "Program") >= 0) yield b.title
    to higher-order functions.
  4. Exercise 11.2.1 Write a function repeatLoop, which should be applied as follows: 
    repeatLoop { command } ( condition )
    Is there also a way to obtain a loop syntax like the following? 
    repeatLoop { command } until ( condition )
  5. Wypróbuj kod z symulacją obwodów scalonych.
  6. Exercise 11.3.2 Another way is to define an or-gate by a combination of inverters and and-gates. Define a function orGate in terms of andGate and inverter. What is the delay time of this function?

Rozwiązania

  1. def isSafe(col: Int, row: Int, queens: List[Int]): Boolean = {
   def isSafeRightDiagonal(col: Int, queens: List[Int]): Boolean = queens match {
       case List() => true
       case head::q => (!(head == col+1) && isSafeRightDiagonal(col+1, q));
   }

   def isSafeLeftDiagonal(col: Int, queens: List[Int]): Boolean = queens match {
       case List() => true
       case head::q => (!(head == col-1) && isSafeLeftDiagonal(col-1, q));
   }

   if(queens.contains(col)) return false
   return isSafeLeftDiagonal(col, queens) && isSafeRightDiagonal(col,queens);
}
    2. lub 
    def queens(n: Int): List[List[Int]] = {
  def placeQueens(k: Int): List[List[Int]] =
    if (k == 0) List(List())
    else for { queens <- placeQueens(k-1)
               column <- List.range(1, n+1)
               if isSafe(column, queens, 1) } yield column :: queens
    placeQueens(n)
}

def isSafe(col: Int, queens: List[Int], delta: Int):Boolean={
  queens match {
    case List() => true
    case y :: ys => if (col != y && col != y+delta && col != y-delta) isSafe(col,ys,delta+1)
      else false
  }
}

  2. def flatten[A](xss: List[List[A]]): List[A] = {
  var acc = List();
  return for(xs <-xss; x<-xs; acc<-x::acc) yield acc;
}

def main(args: Array[String]) = {
  val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))
  Console.print(flatten[Int](diag3));
}

  3. def flatten[A](xss: List[List[A]]) : List[A]= 
  for { li <- xss 
        el <- li } yield el

  4. def findBird (books: List[Book]) = 
  books.foldLeft (List[String]()) ((aku, el) =>
    if (el.authors.exists(a => a startsWith "Bird")) el.title :: aku
      else aku)

def findProgram (books: List[Book]) =
  books.foldLeft (List[String]()) ((aku, el) =>
    if ((el.title indexOf "Program") >= 0) el.title :: aku
      else aku)

  5. def repeatLoop ( command: => Unit ) ( condition: =>  Boolean ) : Unit = {
  command
  if (condition)
    repeatLoop (command) (condition)
}

def until (condition: => Boolean) = condition

var x = 5
repeatLoop { println(x); x = x-1 } ( x > 0 )
repeatLoop { println(x); x = x+1 } (until ( x < 5 ))

  6. 

    7.