Copyright © Cay S. Horstmann 2011

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United
States License.

- If/Else
- Recursion
- Lists

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

`def`

syntax for functionsdef 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 rightval fac = if (x == 0) 1 else x *

**fac**(x - 1) // fac not defined yet - Iteration (
`while`

,`for`

) can always be expressed as recursionTo iterate is human; to recurse, divine (L. Peter Deutsch)

- 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 tailval lst = List(1, 4, 9) lst.head // 1 lst.tail // List(4, 9) lst.tail.tail.tail // Nil

- Use
`::`

to build lists0 :: lst // List(0, 1, 4, 9)

- 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 listsdef squares(n : Int) : List[Int] = if (n == 0) List(0) else n * n :: squares(n - 1)

`lst.tail`

doesn't make a new list—it is a reference to the tail cell- Works because lists are immutable
- Requires garbage collection

- 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.

- 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. - Type
`if (true) 3 else "Hello"`

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

. What do you get? - Type
`val num2 = if (true) 3`

. What do you get? Why?

- An easy way of computing a power
*x*(where^{n}*n*is a nonnegative integer) is given by the recursion*x*^{n}=*x·*x^{n - 1}if*n*> 0*x*^{0}= 1Write a Scala function

`easypow(x : Double, n : Int) : Double`

that implements this algorithm. What is the code of your function? - What is
`easypow(5, 20)`

? - An efficient way of computing a power
*x*(where^{n}*n*is a nonnegative integer) is given by the recursion*x*^{n}=*y*^{2}if*n*is even and positive, where*y*=*x*^{n / 2}*x*^{n}=*x·*x^{n - 1}if*n*is odd*x*^{0}= 1Write a Scala function

`fastpow(x : Double, n : Int) : Double`

that implements this algorithm. What is the code of your function?

- What is the type of
`1 :: 2 :: 3 :: Nil`

? (Just ask the Scala interpreter) - What is the type of
`1 :: "Hello" :: Nil`

? - What happens when you evaluate the expression
`1 :: 2 :: 3`

? Why? - 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) - How do you make a list of the elements
`"Ho",`

using the cons (`"Chi"`

,`"Minh"`

, "City"`::`

) operator?

- 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.

- What is the result of
`concat(List("Ho",`

?`"Chi"`

,`"Minh"`

, "City")) - How can you modify
`concat`

so that it adds spaces between the strings (i.e. so that`concat(List("Ho",`

is`"Chi"`

,`"Minh"`

, "City"))`"Ho Chi Minh City"`

but*not*`"Ho Chi Minh City "`

?