Functional Programming 1

Question 1

What is a higher order function?

Answer 1

A function that acts on other functions

Question 2

What is a first order function?

Answer 2

A function that acts on lists, or other primitives

Question 3

What is a function type? (Give an example)

Answer 3

The type A=>B is the type of a function that takes an argument of type A and returns a result of type B

Question 4

What is the type of a function that maps an integer to an integer

Answer 4

int => int

Question 5

What are function literals sometimes called

Answer 5

Anonymous functions - they do not have a name`

Question 6

What does a theory consist of

Answer 6

1. One or more data types 2. Operations on these data types 3. Laws that describe the relationships between these data types

Question 7

If we want to implement high level concepts following their mathematical theories …

Answer 7

there is no place for mutation

Question 8

A call is said to be in tail position if example ?

Answer 8

the caller does nothing other than return the value of the recursive call: else myrecursivefuntion() is in tail position but else 1 + myrecursivefuntion() is not because there is still work to do when the function returns

Question 9

If all recursive calls made by a function are in tail position, Scala automatically

Answer 9

compiles the recursion to iterative loops that don’t consume call stack frames for each iteration.

Question 10

By default, Scala doesn’t tell us if tail call elimination was successful, but if we’re expecting this to occur for a recursive function we write, we can

Answer 10

tell the compiler about this assumption using the tailrec annotation

Question 11

what does a tailrec annotation look like

Answer 11

@annotation.tailrec or just @tailrec if you have imported the annotation package scala.annotation.tailrec

Question 12

write a method called fib that calculates the fibonacci number of a given integer.

Answer 12

def fib(x: Int): BigInt = { @tailrec def fibHelper(x: Int, prev: BigInt = 0, next: BigInt = 1): BigInt = x match { case 0 => prev case 1 => next case _ => fibHelper(x - 1, next, (next + prev)) } fibHelper(x) }

Question 13

create a method called formatResult that takes a name, an integer and a function that computes a result

Answer 13

def formatResult(name: String, n: Int, f: Int => Int) = { val msg = “The %s of %d is %d.” msg.format(name, n, f(n)) }

Question 14

It’s a common convention to use names like ___________ for parameters to a higher order function

Answer 14

f, g, and h

Question 15

It’s a common convention to use names like f, g, and h for parameters to a higher- order function. In functional programming, we tend to use very short variable names, even one-letter names.

Answer 15

This is usually because HOFs are so general that they have no opinion on what the argument should actually do. All they know about the argu- ment is its type

Question 16

Often, and especially when writing HOFs, we want to write code that works for any type it’s given. These are called

Answer 16

polymorphic functions

Question 17

def findFirstA:Int

Answer 17

A polymorphic function that takes type A as a parameter. And instead of hardcoding an equality check for a given key, take a function with which to test each element of the array.

Question 18

What is a polymorphic function sometimes called

Answer 18

A generic function (Parametric polymorphism)

Question 19

//What is this?

(x: Int) => x == 9

Answer 19

It is a function literal that takes an integer and returns a boolean value depending on whether or not the integer is equal to 9

Question 20

write a function literal that takes two integers and returns a boolean as to whether or not they are equal

Answer 20

(x: Int, y: Int) => x == y

Question 21

When we define a function literal, what is actually being defined in Scala is an object with a

Answer 21

method called apply.

Question 22

What is being returned here?

def partial1A,B,C: B => C

Answer 22

a function that takes in a type B and returns a type C

Question 23

convert a function f of two arguments into a curried function of one argument that partially applies f. def curryA,B,C: A => (B => C)

Answer 23

def curryA, B, C: A => B => C = (a: A) => (b: B) => f(a, b)

Question 24

Implement uncurry, which reverses the transformation of curry. def uncurryA,B,C: (A, B) => C

Answer 24

def uncurryA, B, C: (A, B) => C = (a: A, b: B) => f(a)(b)

Question 25

f andThen g is the same as

Answer 25

g compose f

Question 26

g compose f is the same as

Answer 26

f andthen g

Question 27

A functional data structure is (not surprisingly) operated on using

Answer 27

pure functions

Question 28

a pure function must not ____ or ____

Answer 28

change data in place or perform other side effects

Question 29

what does “sealed” mean when applied as an access modifier to a trait

Answer 29

All implementations of this trait must be declared within this file

Question 30

Cons[+A] what does the + mean

Answer 30

it means that the type parameter A is covariant

Question 31

def applyA: List[A] = if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: _*))

//This is a variadic function - meaning?

Answer 31

It accepts zero of more arguments of type A:

Question 32

Variadic functions are just providing a little syntactic sugar for

Answer 32

creating and passing a Seq of elements explicitly.

Question 33

Implement a function tail for removing the first element of a List.

Answer 33

def tailA = as match { case h :: t => t case Nil => ??? }

Question 34

method(polymorphic) for replacing the item at the head of a list

Answer 34

def setHeadA = h :: tail(t)

Question 35

def factorial(n: Int) Int = if(n-0) 1 else n * factorial(n-1)

//is this a tail recursive function?

Answer 35

No. In order to be a tail recursive function the function needs to call itself as its last action. In this case the result of the call factorial(n-1) needs to be multiplied by n, therefor it is not the last action.

Question 36

What happens when a function call is not tail recursive?

Answer 36

There is a build up of intermediate results - that need to be kept until you can compute a final value.

Question 37

a number x is called a fixed point of a function f if

Answer 37

f(x) = x

Question 38

Generally functions associate to the ____ meaning that sum (cube) (1,10) is the same as

Answer 38

left (sum(cube))(1,10)

Question 39

def sum(f:Int => Int)(a:Int,b:Int):Int = //…

what is the function type

Answer 39

(Int => Int) => (Int, Int) => Int

Question 40

function types associate to the ______ which means that Int => Int => Int is read as

Answer 40

Int => (Int => Int)

Question 41

Mathematically, we call the function which takes an integer as argument and which returns a boolean indicating whether the given integer belongs to a set, the

Answer 41

The characteristic function of the set

Question 42

A type that inherits from any other type

Answer 42

Nothing

Question 43

Type parameters e.g. [T] do not affect evaluation in scala another term for this is

Answer 43

Type erasure

Question 44

Languages that use type erasure include

Answer 44

Java, Scala, Haskell, ML and OCaml

Question 45

Languages that keep type parameters around at runtime include

Answer 45

C++ C# F#

Question 46

What are two principle types of polymorphism

Answer 46

• Subtyping - Generics (Parametric)

Question 47

In Scala all lists are constructed from …

Answer 47

The Empty List Nil and the construction operation Cons

Question 48

what does x :: xs give you

Answer 48

A new list with the first element x followed by the list xs

Question 49

show an example of xs :: xs using fruit

Answer 49

apples :: (oranges :: (pears :: Nil))

Question 50

Convention - Operators ending in : associate … Which means what for a :: b :: c

Answer 50

Right this is interpreted as a :: (b :: c)

Question 51

What are the three fundamental operations on lists through which all other operations can be expressed

Answer 51

IsEmpty Head Tail

Question 52

Write the following method as an insertion sort

def isort(xs: List[Int]): List[Int]

Answer 52

def isort(xs: List[Int]): List[Int] = xs match { case List() => List() case y :: ys => insert(y, isort(ys)) }

Question 53

All lists are constructed from

Answer 53

• The empty list Nil, together with - the construction operation :: cons

Question 54

do an insertion sort

def isort(xs : List[Int]): List [Int]

Answer 54

def isort(xs: List[Int]): List[Int] = xs match { case List() => List() case y :: ys = insert(y, isort(ys)) }

Question 55

xs.length

Answer 55

the number of elements of xs

Question 56

xs.last

Answer 56

the lists last element

Question 57

xs.init

Answer 57

a list consisting of all elements except the last one

Question 58

//implement remove the nth element of the list

def removeAtT:List[T]

Answer 58

def removeAtT:List[T] = (xs take n) ::: (xs drop n + 1)

Question 59

What does the splitAt function do ?

Answer 59

Returns two lists as a pair

1. The list up to the index n
2. The list after the index n

Question 60

// implement a concatenation function using recursion

def concatT:List[T]

Answer 60

def concatT:List[T] = xs match {

case List() => ys

case z :: zs => z :: concat(zs,ys)

}

Question 61

// implement the reverse function

def reverseT:List[T]

Answer 61

def reverseT:List[T] = xs match {

case List() => List()

case List(x) => List(x)

case x :: xs => reverse(xs) ++ List(x)

}

Question 62

def removeAtT:List[T]

Answer 62

def removeAtT:List[T] = xs take n ::: xs drop n+1

Question 63

Create a tuple with the values one, 2 and 3.00 called mytuple

How would you access 3

Answer 63

val mytuple = (“One”,2,3.00)

mytuple._3