Functional Programming 1 Flashcards by Trevor Christie-Taylor

What is a higher order function?

A function that acts on other functions

How well did you know this?

Not at all

Perfectly

What is a first order function?

A function that acts on lists, or other primitives

How well did you know this?

Not at all

Perfectly

What is a function type? (Give an example)

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

How well did you know this?

Not at all

Perfectly

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

int => int

How well did you know this?

Not at all

Perfectly

What are function literals sometimes called

Anonymous functions - they do not have a name`

How well did you know this?

Not at all

Perfectly

What does a theory consist of

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

How well did you know this?

Not at all

Perfectly

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

there is no place for mutation

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

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

tell the compiler about this assumption using the tailrec annotation

How well did you know this?

Not at all

Perfectly

what does a tailrec annotation look like

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

How well did you know this?

Not at all

Perfectly

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

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) }

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

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

f, g, and h

How well did you know this?

Not at all

Perfectly

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.

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

How well did you know this?

Not at all

Perfectly

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

polymorphic functions

How well did you know this?

Not at all

Perfectly

def findFirstA:Int

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.

How well did you know this?

Not at all

Perfectly

What is a polymorphic function sometimes called

A generic function (Parametric polymorphism)

How well did you know this?

Not at all

Perfectly

//What is this?

(x: Int) => x == 9

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

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

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

method called apply.

How well did you know this?

Not at all

Perfectly

What is being returned here?

def partial1A,B,C: B => C

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

How well did you know this?

Not at all

Perfectly

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)

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

How well did you know this?

Not at all

Perfectly

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

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

How well did you know this?

Not at all

Perfectly

f andThen g is the same as

g compose f

g compose f is the same as

f andthen g

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

pure functions

a pure function must not ____ or \_\_\_\_

change data in place or perform other side effects

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

All implementations of this trait must be declared within this file

Cons[+A] what does the + mean

it means that the type parameter A is covariant

def apply[A](as: A\*): List[A] = if (as.isEmpty) Nil else Cons(as.head, apply(as.tail: \_\*)) //This is a variadic function - meaning?

It accepts zero of more arguments of type A:

Variadic functions are just providing a little syntactic sugar for

creating and passing a Seq of elements explicitly.

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

def tail[A](as: List[A]) = as match { case h :: t =\> t case Nil =\> ??? }

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

def setHead[A](h: A, t: List[A]) = h :: tail(t)

def factorial(n: Int) Int = if(n-0) 1 else n \* factorial(n-1) //is this a tail recursive function?

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.

What happens when a function call is not tail recursive?

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

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

f(x) = x

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

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

def sum(f:Int =\> Int)(a:Int,b:Int):Int = //... what is the function type

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

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

Int =\> (Int =\> Int)

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

The characteristic function of the set

A type that inherits from any other type

Nothing

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

Type erasure

Languages that use type erasure include

Java, Scala, Haskell, ML and OCaml

Languages that keep type parameters around at runtime include

C++ C# F#

What are two principle types of polymorphism

- Subtyping - Generics (Parametric)

In Scala all lists are constructed from ...

The Empty List Nil and the construction operation Cons

what does x :: xs give you

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

show an example of xs :: xs using fruit

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

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

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

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

IsEmpty Head Tail

Write the following method as an insertion sort def isort(xs: List[Int]): List[Int]

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

All lists are constructed from

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

do an insertion sort def isort(xs : List[Int]): List [Int]

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

xs.length

the number of elements of xs

xs.last

the lists last element

xs.init

a list consisting of all elements except the last one

//implement remove the nth element of the list def removeAt[T](xs:List[T], n:Int):List[T]

def removeAt[T](xs:List[T], n:Int):List[T] = (xs take n) ::: (xs drop n + 1)

What does the splitAt function do ?

Returns two lists as a pair 1. The list up to the index n 2. The list after the index n

// implement a concatenation function using recursion def concat[T](xs:List[T],ys:List[T]):List[T]

def concat[T](xs:List[T],ys:List[T]):List[T] = xs match { case List() =\> ys case z :: zs =\> z :: concat(zs,ys) }

// implement the reverse function def reverse[T](xs:List[T]):List[T]

def reverse[T](xs:List[T]):List[T] = xs match { case List() =\> List() case List(x) =\> List(x) case x :: xs =\> reverse(xs) ++ List(x) }

def removeAt[T](xs:List[T], n:Int):List[T]

def removeAt[T](xs:List[T], n:Int):List[T] = xs take n ::: xs drop n+1

Create a tuple with the values one, 2 and 3.00 called mytuple How would you access 3

val mytuple = ("One",2,3.00) mytuple.\_3