• 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.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
• 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)
• 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 xn (where n is a nonnegative integer) is given by the recursion

xn = xn - 1 if n > 0

x0 = 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 xn (where n is a nonnegative integer) is given by the recursion

xn = y2 if n is even and positive, where y = xn / 2

xn = xn - 1 if n is odd

x0 = 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 "`?