Recursion Flashcards
Do you need to declare the type of a variable in a functional programming language like Scala?
No as Scala has type inference, so its rarely necessary to declare the type of a variable.
What is a pure function?
Pure functions are functions that have no side effects. This can have some good benefits for execution purposes:
- Any unused expressions can be removed
- If the arguments have no side effects, the function will return the same result as the previous time (referential integrity)
- If there’s no dependency between two pure function calls, they can be done in either order or in parallel concurrently
- The compiler can then reorder the program execution to optimize efficiency
Not all functions can be pure such as I/O functions
Lazy Evaluation - Why do it?
Lazy evaluation means that the expressions are only evaluated when they are required. The expression Func(34), 34 would only be passed to the function and evaluated when it is used.
It can improve efficiency and provide a useful way of implementing non-terminating sequences
Recursion & Tail-Recursion
In Scala, if you are using recursion you must specify the return type.
Recursion is not without its problems. Every new iteration is essentially a new function call, a new stack frame gets pushed for each step. This can make the stack grow unnecessarily large and make some calculations fail for a lack of resources. (Causing stack overflow)
Tail recursion prevents stack overflow by having the last instruction in a function be the recursive call. This means that you can re-use the same stack frame and ultimately prevents stack overflow from happening.
Is it possible to re-write non-tail recursive algorithms?
Yes, you can do that to make it tail recursive. Ideally, we don’t want to have to change the function definition but instead introduce a nested function within that function as the tail recursive method
What is the difference between pass by value and pass by name in Scala?
Pass by value parameters are calculated on the call of function whereas pass by name parameters are calculated on each use of the parameters.
Pass by value parameters are really a copy of the value passed to the function whereas pass by name may never be calculated if the parameter is never used.
Passing by name uses the => symbol (Known as the Fat arrow or the Rocket) and pass by value doesn’t have it.
What is currying?
Currying in essence is where a function that takes multiple arguments can be re-written as a composite of functions that take single arguments. We can’t call the curried function with the arguments presented as a list and instead what is happening the call of the function with the first argument, then composing the result of that with the result of calling the function again on the second one.
Example:
def mult(a: Int, b: Int) = a * b
mult: (a: Int, b: Int) Int
mult(3, 4)
res30: Int = 12
def curryMult(a: Int)(b: Int) = a * b
curryMult: (a: Int)(b: Int) Int //Note that the a and b are wrapped as their own individual single parameter functions as curried functions can’t take multiple parameters when specified like ()()
Curried methods can be used to define new control structures i.e. resource management - a try with resources, a synchronised block or working with a database connection.
What is meant by a partial function in Scala?
Partially defined functions are functions that are not defined over an entire domain. This is not the same as partially applied functions. PartialFunction is a subtype of Function1 but has two additional methods
- def isDefinedAt(a: A) Boolean
- orElse(that: PartialFunction[A,B]): PartialFunction[A,B]
To define a partial function, we can use cases or we can provide implementations for the methods for isDefineAt, orElse and importantly the apply method which gives the appearance of a function call on an object so we can use that to do the work for us
Can you Map as Partial Functions?
Yes, we can view some collections as functions like in sequence maps a key onto some other value. A map does the same thing but doesn’t restrict the domain to a specific type like Int. However, the mapping doesn’t need to be defined for all values in the type of the key, so we can treat a map or a Seq as a partial function.
What do exceptions look like in Scala?
Since Scala runs on the JVM, it can take advantage of Java’s existing exception syntax with a functional twist. Scala unlike Java does NOT support checked exceptions and as such all exceptions are runtime exceptions. Exception handling is achieved through a variation of pattern matching.
try {
val i: Int = “123”.toInt
} catch {
case e: NumberFormatException => println (“oops”)
}
Whilst this is fine it is a bit clumsy and can create lots of try’s and catches, as well as making it difficult to multi-thread code as the try and catch code is by definition executed on the same thread. So it can be difficult to deal with a situation where a call is dispatched on a separate thread, often transparently to the caller.
The try catch approach doesn’t fit well with the functional approach that is encouraged by Scala in that exceptions are essentially a mutable state that makes it hard to reason about the code.
Try Catch As An Expression
The try and catch block returns a value in Scala that can be assigned and used further in the program. If we had tried to force things to be a specific type like int, then the code wouldn’t always compile as the value returned from the failure path may not always be int.
Retaining type information, the failure path needs to be able to return a value of the same type as the success path. This could be 0 for success and 1 for failure just as an example. However, now the caller needs to figure out if the result value is a value returned due to an exception or a value returned in an expression that worked inside the try block.
To fix this, we can use the Option[T] type in scala which is used to represent success or failure. Some(t: T) means success and None means failure. These are very much like Optionals in Java or Nullables in C#
The either type
Either[A,B] is a union type that contains the instance of A or the instance of B. This can also be used in exception handling. There are two subtypes, Left and Right. If the value is of type A then the Either will contain Left otherwise will be Right.
The compiler ensures this rule is followed. Values of Either type can be examined using pattern matching. In use for exceptions, Left should be for the exception and the right should be for the success value. This allows you to access the Exception object.
Either for exceptions doesn’t support map or flatmap directly but it can work if you project to left or right before hand. Either[A, B] is an unbiased type where the use of Left is to store the exceptions details by convention.
Try[T]
In Scala 2.10, the Union Type Try[T] was added and it has two subclasses: Success[T] and Failure[T] where Success[T] contains the value and Failure[T] contains the throwable. Try[T] is a monad type and does support maps and flatmaps as well as any other higher order functions.
It can offer implementations of the combinator functions map, foreach, flatMap, filter etc. that don’t form part of Either[A,B]. This makes it easier to build more sophisticated compositions of functions based on this type
The flatMap makes it possible to do Try[T] in for comprehensions as the behaviour is to pass on whatever the result was seen in the previous stage of the pipeline processing it further if it was a Success or simply passing it on without processing if it was a Failure
Try[T] Recovering from exceptions
Try[T] supports the recover method which returns ‘this’ if it was a Success and apply function on ‘this’ if it was a Failure. By executing the function, it allows it to recover from an exception
What are implicit definitions?
Scala enables us to have definitions inserted by the compiler when necessary including methods, method parameters and more recently classes. This is useful for converting one type to another, flexible default values for parameters and adding further mechanisms for bounding type parameters.
Something that is implicit can be defined as such within objects, classes, package objects etc. but can’t be defined at the top level in the code.
