Return to chapter index

23 For Expressions Revisited

Sample run of chapter's interpreter examples

• 23.1 For expressions
• 23.2 The n-queens problem
• 23.3 Querying with for expressions
• 23.4 Translation of for expressions
• 23.5 Going the other way
• 23.6 Generalizing for
• 23.7 Conclusion

  scala> case class Person(name: String, 
                           isMale: Boolean, 
                           children: Person*)


// In file for-expressions/Misc.scala

  val lara = Person("Lara", false)
  val bob = Person("Bob", true)
  val julie = Person("Julie", false, lara, bob)
  val persons = List(lara, bob, julie)


  scala> persons filter (p => !p.isMale) flatMap (p =>
       |     (p.children map (c => (p.name, c.name))))
  res0: List[(String, String)] = List((Julie,Lara), 
  (Julie,Bob))


  scala> persons withFilter (p => !p.isMale) flatMap (p =>
       |     (p.children map (c => (p.name, c.name))))
  res1: List[(String, String)] = List((Julie,Lara), 
      (Julie,Bob))


  scala> for (p <- persons; if !p.isMale; c <- p.children) 
       | yield (p.name, c.name)
  res2: List[(String, String)] = List((Julie,Lara), 
      (Julie,Bob))


  

23.1 For expressions

  for ( seq ) yield expr


// In file for-expressions/Misc.scala

  for (p <- persons; n = p.name; if (n startsWith "To")) 
  yield n


// In file for-expressions/Misc.scala

  for {
    p <- persons              // a generator
    n = p.name                // a definition
    if (n startsWith "To")    // a filter
  } yield n


  pat <- expr


  pat = expr


  val x = expr


  if expr


  scala> for (x <- List(1, 2); y <- List("one", "two")) 
       | yield (x, y)
  res3: List[(Int, java.lang.String)] = 
    List((1,one), (1,two), (2,one), (2,two))


  

23.2 The n-queens problem

// In file for-expressions/Misc.scala

  def queens(n: Int): List[List[(Int, Int)]] = {
    def placeQueens(k: Int): List[List[(Int, Int)]] =
      if (k == 0) 
        List(List())
      else 
        for {
          queens <- placeQueens(k - 1)
          column <- 1 to n
          queen = (k, column)
          if isSafe(queen, queens) 
        } yield queen :: queens

    placeQueens(n)
  }


// In file for-expressions/Misc.scala

  def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = 
    queens forall (q => !inCheck(queen, q))

  def inCheck(q1: (Int, Int), q2: (Int, Int)) = 
    q1._1 == q2._1 ||  // same row
    q1._2 == q2._2 ||  // same column
    (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // on diagonal


  

23.3 Querying with for expressions

  case class Book(title: String, authors: String*)


  val books: List[Book] =
    List(
      Book(
        "Structure and Interpretation of Computer Programs",
        "Abelson, Harold", "Sussman, Gerald J."
      ),
      Book(
        "Principles of Compiler Design",
        "Aho, Alfred", "Ullman, Jeffrey"
      ),
      Book(
        "Programming in Modula-2",
        "Wirth, Niklaus"
      ),
      Book(
        "Elements of ML Programming",
        "Ullman, Jeffrey"
      ),
      Book(
        "The Java Language Specification", "Gosling, James",
        "Joy, Bill", "Steele, Guy", "Bracha, Gilad"
      )
    )


  scala> for (b <- books; a <- b.authors
       |      if a startsWith "Gosling")
       | yield b.title
  res4: List[String] = List(The Java Language Specification)


  scala> for (b <- books if (b.title indexOf "Program") >= 0)
       | yield b.title
  res5: List[String] = List(Structure and Interpretation of 
    Computer Programs, Programming in Modula-2, Elements
      of ML Programming)


  scala> for (b1 <- books; b2 <- books if b1 != b2;
       |     a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
       | yield a1
  res6: List[String] = List(Ullman, Jeffrey, Ullman, Jeffrey)


  scala> def removeDuplicates[A](xs: List[A]): List[A] = {
       |   if (xs.isEmpty) xs
       |   else
       |     xs.head :: removeDuplicates(
       |       xs.tail filter (x => x != xs.head)
       |     )
       | }
  removeDuplicates: [A](xs: List[A])List[A]

  scala> removeDuplicates(res6)
  res7: List[String] = List(Ullman, Jeffrey)


// In file for-expressions/Misc.scala

   xs.head :: removeDuplicates(
     for (x <- xs.tail if x != xs.head) yield x
   )


  

23.4 Translation of for expressions

for (b1 <- books; b2 <- books if b1 != b2;
     a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1


books flatMap (b1 =>
  books withFilter (b2 => b1 != b2) flatMap (b2 =>
    b1.authors flatMap (a1 =>
      b2.authors withFilter (a2 => a1 == a2) map (a2 =>
        a1))))


// In file for-expressions/Misc.scala

  for (x <- 1 to 1000; y = expensiveComputationNotInvolvingX)
  yield x * y


// In file for-expressions/Misc.scala

  val y = expensiveComputationNotInvolvingX
  for (x <- 1 to 1000) yield x * y


// In file for-expressions/Misc.scala

  var sum = 0
  for (xs <- xss; x <- xs) sum += x


// In file for-expressions/Misc.scala

  var sum = 0
  xss foreach (xs => 
    xs foreach (x =>
      sum += x))


  

23.5 Going the other way

// In file for-expressions/Misc.scala

  object Demo {
    def map[A, B](xs: List[A], f: A => B): List[B] =
      for (x <- xs) yield f(x)

    def flatMap[A, B](xs: List[A], f: A => List[B]): List[B] =
      for (x <- xs; y <- f(x)) yield y

    def filter[A](xs: List[A], p: A => Boolean): List[A] =
      for (x <- xs if p(x)) yield x
  }


  

23.6 Generalizing for

// In file for-expressions/Misc.scala

  abstract class C[A] {
    def map[B](f: A => B): C[B]
    def flatMap[B](f: A => C[B]): C[B]
    def withFilter(p: A => Boolean): C[A]
    def foreach(b: A => Unit): Unit
  }


  

23.7 Conclusion