Functional Programming in Scala

• If/Else
• Recursion
• Lists

If/Else

• if (booleanExpression) expression1 else expression2

• if/else is an expression, not a statement. Can be used in other expressions:

  val x = (if (true) 2 else 4) * 3

• Like ? : in Java
• Type is the most specific supertype common to expression1, expression2

  val x = if (true) 3 else 3.14 // type is AnyVal

• Omitting the else yields type Unit (like void in Java); not useful in functional programming

Recursion

• def syntax for functions

  def triple(x : Int) = 3 * x
  // same as val triple = (x : Int) => 3 * x

• With recursive functions, also need to specify return type:

  def fac(x : Int) : Int = if (x == 0) 1 else x * fac(x - 1)

• Need def because the name is used on the right

  val fac = if (x == 0) 1 else x * fac(x - 1) // fac not defined yet

• Iteration (while, for) can always be expressed as recursion

  To iterate is human; to recurse, divine (L. Peter Deutsch)

Lists

• Very different from Java lists. No iterators
• Three primitives: head, tail, cons (written as ::)
• A list is either empty (Nil) or has a head and tail

  val lst = List(1, 4, 9)
  lst.head // 1
  lst.tail // List(4, 9)
  lst.tail.tail.tail // Nil

• Use :: to build lists

  0 :: lst // List(0, 1, 4, 9)

List Functions

• Use recursion for list functions

  def sum(lst : List[Int]) : Int = 
    if (lst.isEmpty) 
      0 else // NOTE: else must be on this line
      lst.head + sum(lst.tail)

• Use :: to recursively build lists

  def squares(n : Int) : List[Int] = 
    if (n == 0) 
      List(0) else
      n * n :: squares(n - 1)

Why This Isn't Inefficient

• lst.tail doesn't make a new list—it is a reference to the tail cell

  

• Works because lists are immutable
• Requires garbage collection

Lab

• Format of classes: approx. 20 minutes lecture, 45 minutes lab, 10 minute wrap-up
• Use your laptop (with JDK 1.6 installed)
• Work with a buddy
• One of you fusses with the code, the other types up answers
• Switch roles each time
• Submit lab work to eCampus.

Step 1: If/Else

1. Open a shell window and type scala. Type if (true) 3 else 4. As always, don't type the period, but type ENTER. What do you get?

   HINT: These “What do you get” exercises are a lot more effective when you and your buddy first discuss whar you think you'll get. “Form a hypothesis” is an essential part of the learning path.

2. Type if (true) 3 else "Hello". What do you get? How is it different from the previous result? Why?
3. Type val num = if (true) 3 else 4. What do you get?
4. Type val num2 = if (true) 3. What do you get? Why?

Step 2: Recursion

1. An easy way of computing a power xⁿ (where n is a nonnegative integer) is given by the recursion

   xⁿ = x· x^{n - 1} if n > 0

   x⁰ = 1

   Write a Scala function pow(x : Double, n : Int) : Double that implements this algorithm. What is the code of your function?

2. What is pow(5, 20)?
3. (If you have extra time) An efficient way of computing a power xⁿ (where n is a nonnegative integer) is given by the recursion

   xⁿ = y² if n is even and positive, where y = x^{n / 2}

   xⁿ = x· x^{n - 1} if n is odd

   x⁰ = 1

   Write a Scala function pow(x : Double, n : Int) : Int that implements this algorithm. What is the code of your function?

Step 3: Lists

1. What is the type of 1 :: 2 :: 3 :: Nil? (Just ask the Scala interpreter)
2. What is the type of 1 :: "Hello" :: Nil?
3. What happens when you evaluate the expression 1 :: 2 :: 3? Why?
4. How do you make a list of the elements "San", "Jose", "State" using a list constructor? (Be sure to try your answer in the Scala interpreter)
5. How do you make a list of the elements "San", "Jose", "State" using the cons (::) operator?

Step 4: List Functions

1. Write a recursive function concat that concatenates all strings in a List[String], yielding a String. Hint: concat(Nil) is "". What is concat(lst) in terms if lst.head, lst.tail? Give the code of your function.
2. What is the result of concat(List("San","Jose"))?
3. (If you have extra time) How can you modify concat so that it adds spaces between the strings (i.e. so that concat(List("San","Jose")) is "San Jose"?