Functional Programming 1 Flashcards
What is a higher order function?
A function that acts on other functions
What is a first order function?
A function that acts on lists, or other primitives
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
What is the type of a function that maps an integer to an integer
int => int
What are function literals sometimes called
Anonymous functions - they do not have a name`
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
If we want to implement high level concepts following their mathematical theories …
there is no place for mutation
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
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.
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
what does a tailrec annotation look like
@annotation.tailrec or just @tailrec if you have imported the annotation package scala.annotation.tailrec
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) }
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)) }
It’s a common convention to use names like ___________ for parameters to a higher order function
f, g, and h
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
Often, and especially when writing HOFs, we want to write code that works for any type it’s given. These are called
polymorphic functions
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.
What is a polymorphic function sometimes called
A generic function (Parametric polymorphism)
//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
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
When we define a function literal, what is actually being defined in Scala is an object with a
method called apply.
What is being returned here?
def partial1A,B,C: B => C
a function that takes in a type B and returns a type C
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)
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)
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 applyA: 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 tailA = as match { case h :: t => t case Nil => ??? }
method(polymorphic) for replacing the item at the head of a list
def setHeadA = 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 removeAtT:List[T]
def removeAtT:List[T] = (xs take n) ::: (xs drop n + 1)
What does the splitAt function do ?
Returns two lists as a pair
- The list up to the index n
- The list after the index n
// implement a concatenation function using recursion
def concatT:List[T]
// implement the reverse function
def reverseT:List[T]
def reverseT:List[T] = xs match {
case List() => List()
case List(x) => List(x)
case x :: xs => reverse(xs) ++ List(x)
}
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
