Copyright © Cay S. Horstmann 2015

This work is licensed under a Creative Commons Attribution 4.0 International License

`def`

- So far, we always used
`val`

to define functionsval triple = (x: Double) => 3 * x

- It is more common to use def:
def triple(x: Double) = 3 * x

- Caution: If
`def`

isn't followed by`=`

, you are defining a function returning`()`

def triple(x: Double) { 3 * x } // Returns ()!

- With recursive functions, must specify return type
def fac(n: Int)

**:Int**= ...

- Functions that take other functions as parameters or that return functions as results are called higher order functions.
- Take the sum of the integers between a and b:
def sumInts(a: Int, b: Int): Int = a.to(b).reduce(_+_)

- Take the sum of the squares of all the integers between a and b :
def square(x: Int): Int = x * x def sumSquares(a: Int, b: Int): Int = a.to(b).map(square).reduce(_+_)

- Take the sum of the cubes of all the integers between a and b :
def cube(x: Int): Int = x * x * x def sumCubes(a: Int, b: Int): Int = a.to(b).map(cube).reduce(_+_)

- We can factor out the common pattern of these three functions as following:
def sum(f: Int => Int, a: Int, b: Int): Int = a.to(b).map(f).reduce(_+_)

- We use a function that takes another function as parameter.
def sumInts(a: Int, b: Int) = sum(id, a, b) def sumSquares(a: Int, b: Int) = sum(squares, a, b) def sumCubes(a: Int, b: Int) = sum(cube, a, b)

- Where
def id(x: Int): Int = x def square(x: Int): Int = x * x def cube(x: Int): Int = x * x * x

- We can even be shorter by getting rid of these parameters:
def sum(f: Int => Int): (Int, Int) => Int = (a: Int, b: Int) =>a.to(b).map(f).reduce(_+_)

- sum is now a function that returns another function. The returned function applies the given function parameter f and sums the results.

sum(square)(1,4)

- A syntax error—the argument to
`sum`

must be a paire of Ints - Is equivalent to
`sumSquares(1,4)`

- Is equivalent to sum(1,4)(square)
- Returns 30

- We can then define:
def sumInts = sum(id) def sumSquares = sum(square)

def sumCubes = sum(cube) - These functions can in turn be applied like any other function:
sumCubes(1, 10) + sumSquares(10, 20)

- With the last definition of sum we can also call the functions as following
sum (cube) (1, 10)

- sum(cube) applies sum to cube and returns the sum of cubes function.
- sum(cube) is therefore equivalent to sumCubes.
- This function is next applied to the arguments (1, 10).
- Generally, function application associates to the left:
sum(cube)(1, 10) == (sum (cube)) (1, 10)

- This style of definition and function application is called currying, named for its instigator, Haskell Brooks Curry (1900-1982), a twentieth century logician.

`Seq[A].corresponds(t: Seq[B])(p: (A, B) => Boolean)`

checks whether two sequences have “corresponding” elements, as defined by`p`

- For example,
val s = "Mary had a little lamb".split(" ") val t = Array(4, 3, 1, 6, 4) s.corresponds(t)((a: String, b: Int) => a.length == b)

- Or more concisely
s.corresponds(t)(_.length == _)

- Why the currying
s.corresponds(t)

**(_.length == _)** - Otherwise, type inference wouldn't work. The type of
`t`

is needed to infer the type`B`

- The product of the elements in
`Vector(a, b, c)`

is`a * b * c = 1 * a * b * c = ((1 * a) * b) * c`

- Use
`foldLeft`

:def prod(lst: Vector[Int]) = lst.foldLeft(1) (_ * _)

* / \ * c / \ * b / \ 1 a

- The first argument of the folding function is the partial answer; the second is the new list value to be considered
- The
`foldRight`

operator works right-to-left:`a * (b * (c * 1))`

- That's useful for right-associative operators (e.g. list construction)

1.to(10).foldLeft("")(_ + _)

`"12345678910"`

`"10987654321"`

- 55
- Something else (syntax error, other result, ...)

- We could have computed the multiplication function with
`reduce`

- But
`reduce`

only works with operators`(A, A) => A`

`foldLeft`

works with any operator`(B, A) => B`

- Remember this from the last lab?
augment(augment(augment(

**Vector(Vector("1"))**, '2'), '3'), '4') - We couldn't use
`reduce`

because`augment`

takes arguments of different typesval augment = (a: Vector[Vector[String]], t: Char) => ...

- It's easy with
`foldLeft`

—see lab

*Any*recursive definition of the form`f(n) = {(s , if n = 0),(t(f(n - 1), n) , if n > 0):}`

can be computed with a fold.1.to(n).foldLeft(s)(t)

- Example: Factorial (`s = 1`, `t = \_ * \_`)
`n! = {(1 , if n = 0),((n - 1)! * n , if n > 0):}`

- Example: Subsets of `{ 1 ... n }`
`S(n) = {({} , if n = 0),(S(n - 1) ∪ { s ∪ {n} | s ∈ S(n - 1) } , if n > 0):}`

- Task: Get letter frequencies of a string
- E.g.
`"Mississippi"`

→`Map(M -> 1, i -> 4, s -> 4, p -> 2)`

- E.g.
- Can update a mutable map of counters—but not with our Scala subset ☺
- How about an immutable map? Produce a new map in each step
. . . op / \ op 's' / \ op 'i' / \ empty map 'M'

- What is
`op`

?(m, c) => m + (c -> (m.getOrElse(c, 0) + 1))

- You work with a buddy
- One of you (the coder) writes the code, the other (the scribe) types up answers
- When you get stuck, ask your buddy first!
- Switch coder/scribe roles each lab
- The coder submits the worksheet. Include the scribe's name in the worksheet!
- The scribe submits answers. Include the coder's name in the report!

- Here is a function of computing the “maximum” string in a list that works for any ordering.
def max(lst : Seq[String], less : (String, String) => Boolean) = lst.reduce((x, y) => if (less(x, y)) y else x)

Make a call to

`max`

that yields the longest string in a sequence of strings.*Important:*Use`_`

for the string parameters in your`less`

function. - Now we'll make this generic. Don't worry—it won't hurt a bit:
def max

**[T]**(lst : Seq**[T]**, less : (**T**,**T**) => Boolean) = lst.reduce((x, y) => if (less(x, y)) y else x)What happens when you call

`max(lst, _ < _)?`

- Ok, that didn't work so well. Currying to the rescue. Curry the
`max[T]`

function, exactly like`mul2`

above. What is the code for your revised function? What happens when you call`max2(lst)(_ < _)`

? - Why does the second approach work with
`_`

parameters?

- How do you compute `n!` with a fold?
val fac = (n: Int) => ...

- How do you compute `n!` with a reduce?
- How do you compute `n!` with a recursive function?
- Now on to those subsets where your eyes probably glazed over. We want
`subsets(2)`

to be`Vector(Vector(), Vector(1), Vector(`

. How do you get that out of**2**), Vector(1,**2**))`subsets(1)`

, i.e.`Vector(Vector(), Vector(1))`

? - Ok, what's that in Scala? You are given a vector of vectors
`s`

and an integer`n`

, and you want`s`

together with the sequence obtained by adding`n`

to all elements of`s`

. Write a function that does that, and test it. - Now write
`subsets`

by using`foldLeft`

. - It is also easy to write
`subsets`

as a recursive function. Try it! - Complete and test the
`letterFrequencies`

function from the slide 12. What do you get for`letterFrequencies("Mississippi")`

?

- Last time, we got stuck with repeatedly calling
`augment`

to get all ways of breaking up a string into substrings. For example, here are all substrings of`"1234"`

augment(augment(augment(Vector(Vector("1")), '2'), '3'), '4')

Get last week's worksheet from your buddy and copy over all you need to today's worksheet. - Now we want this to work for arbitrary strings, not just
`"1234"`

. Of course, we want to use`foldLeft`

with`augment`

. What is the seed value? And to what sequence do you apply`foldLeft`

? - Implement
`val substrings = (s: String) => ...`

. What is`substrings("2728")`

? - Note that's a vector of
`Vector[String]`

. The shining achievement of last week's lab was the function`wordsForDigitSequence`

that found all words for such a sequence. What do you get when you callsubstrings("2728").map(wordsForDigitsSequence)

- Ok, that's not quite what we want. How do you fix it?
- Now implement
`val phoneMnemonics = (digits: String) => ...`

that does this for any string of digits, not just`"2728"`

. What is`phoneMnemonics("7225247386")`

? (You can change the cutoff limit of the worksheet in the preferences to see all solutions.)