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 C++
• Type is the most specific supertype common to expression1, expression2

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

• Omitting the else yields type Unit (like void in C++); 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 C++ linked lists. No iterators
• Three primitives: head, tail, :: (pronounced cons)
• 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

• Use the computer in front of you
• Or bring your laptop (Scala installation instructions at the end of the previous slide set)
• You work with a buddy
• One of you writes the code (coder), the other types up answers (scribe)
• When you get stuck, ask your buddy first!
• Switch roles each lab. The previous scribe is the coder for this lab.
• Submit lab work to Sakai.

Step 1: If/Else

1. Open the Scala interpreter, like in the previous lab.

   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 what you think you'll get before you hit ENTER. “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 easypow(x : Double, n : Int) : Double that implements this algorithm. What is the code of your function?

2. What is easypow(5, 20)?
3. 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 fastpow(x : Double, n : Int) : Double 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 "Ho", "Chi", "Minh", "City" using a list constructor? (Be sure to try your answer in the Scala interpreter)
5. How do you make a list of the elements "Ho", "Chi", "Minh", "City" 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: (1) String concatenation is + in Scala, just like in C++. (2) concat(Nil) is "". (3) Think about concat(lst) in terms of lst.head, lst.tail.

   Give the code of your function.

2. What is the result of concat(List("Ho", "Chi", "Minh", "City"))?
3. How can you modify concat so that it adds spaces between the strings (i.e. so that concat(List("Ho", "Chi", "Minh", "City")) is "Ho Chi Minh City" but not "Ho Chi Minh City "?