You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Let's define the size of this and that as n. As usual with big-O notation, we assume approximately the same size here; we're only interested how the order of magnitude changes with increasing set sizes.
union1 recurses into right and left, each containing about n/2 elements. For each element we call incl, which effectively does an insert sort in a binary tree (this is O(log(n))). Combined, the complexity is O(n * log(n)).
union2 recurses into right and right.union(that), thus the complexity for the recursion is O(n/2) + O(n/2 * n) = O(n) + O(n^2) = O(n^2). As all implementations call incl, the combined complexity is O(n^2 * log(n)^2).
union3 recurses identically to union1, for complexity O(n * log(n)). However, we get some improvement due to tail recursion. This is due to mechanical sympathy (we use less stack space, causing less CPU cache invalidation) but does not reduce the big-O complexity.
A <: B -- A is a subtype of B. That means that “everything that can be done with an object of type B can also be done with an object of type A” (Liskov substitution principle).
A >: B -- A is a supertype of B (means that B <: A).
Function types:
If A2 <: A1 and B1 <: B2, then (A1 => B1) <: (A2 => B2).
Why is that?
Functions of type A2 => B2 take a parameter of type A2; hence all parameters that can be fed into it can also be fed to a function of type A1 => B1, because A2 is a subtype of A1.
Functions of type A1 => B1 return a value of type B1; because of the type relationships, all B1s are also B2s. So every A2 value passed to a function of type A1 => B1 is also a B2, making that function also of type A2 => B2.
Notation change:
If Ac <: Ap and Bc <: Bp, then (Ap => Bc) <: (Ac => Bp)
If mammal <: animal and banana <: food, then (animal => fruit) <: (mammal => food)
Conclusions:
Every function that takes an A can also be said to take any subtype of A.
Every function that returns a B can also be said to return any supertype of B.
Reasoning:
In set notation, the phrase "every X is also a Y" means that all X's are contained in the set of all Y's. So, X < Y.
In type notation, if every value of type X is also a value of type Y, then X is a subtype of Y. So, X <: Y.
"animal-taking function" is a subtype of "mammal-taking function". This means that every animal-taking function can also be seen as a mammal-taking function.
"fruit-returning function" is a special case of "food-returning function". Every fruit-returning function is also a food-returning function.
So (A => _) is a subtype of (T => _)[T <: A], and (_ => B) is a subtype of (_ => T)[B <: T].
Functions are covariant on their return types and contravariant on their parameter types.
In Scala, +T denotes a covariant type parameter, and -T denotes a contravariant type parameter. Just T denotes a nonvariant type parameter, that is, parameterized types with related type parameters are not related.
Function types
A function type is represented in Scala via a trait. A function which takes one argument maps to the Function1 trait:
trait Function1[-T, +U] {
def apply(x: T): U
}
What if a method were a function? Well, to apply a method to a set of parameters, we would first have to resolve it as the apply method of a Function trait; then, to apply the apply method, we would need to translate it into the application of another apply method. This would not end.
So maybe a method is simply a “signature” of a function.
When to use (co|contra|non)variance
Contravariant type parameters can only appear in method parameters.
Covariant type parameters can only appear in method results.
Nonvariant type parameters can appear anywhere.
By making our List class covariant (List[+T]), we may express Nil as a singleton object, instead of a generic class! We define Nil as an instance of List[Nothing], because Nothing <: T for any T, hence List[Nothing] <: List[T]. So Nil is an instance of any List[T] type.
That fits well into our previous definition of Nil#head and Nil#tail as having Nothing return type.
However, we cannot do something like this:
abstract class List[+T] {
def prepend(elem: T): List[T] = new Cons(elem, this)
}
because that violates variance checking. Furthermore, this kind of method would violate the Liskov substitution principle. Suppose a Set type with two subtypes, object Empty and class NonEmpty; and a list xs of type List[Set]:
xs.prepend(Empty)
The same operation on a list ys of type List[NonEmpty] would lead to a type error:
ys.prepend(Empty)
^ type mismatch
required: NonEmpty
found: Empty
So, List[NonEmpty] cannot be a subtype of List[Set] when it contains such a prepend method.
Type bounds
To make the prepend method correct, we can use type bounds:
In this case we set T as a lower bound for type U.
Covariant type parameters may appear in lower bounds of method type parameters
Contravariant type parameters may appear in upper bounds of method type parameters
Decomposition
Decomposition: Access objects in an extensible class hierarchy.
Failed attempts:
Classification and accessor methods: too much code
Type tests and casts: unsafe and low-level
Object-oriented decomposition:
Need to touch all classes to add a new operation
Does not always work. Example: simplifying arithmetical operations is a non-local operation and requires working with multiple objects.
Pattern matching
The sole purpose of test and accessor functions is to reverse the construction process:
Which class was used?
Which parameters were used in the constructor?
Case classes
trait Expr
case class Number(n: Int) extends Expr
case class Sum(e1: Expr, e2: Expr) extends Expr
This also implicitly defines auxiliary objects:
object Number {
def apply(n: Int) = new Number(n)
}
Number(1) // Now equivalent to `new Number(1)`
match
def eval(e: Expr): Int = e match {
case Number(n) => n
case Sum(e1, e2) => eval(e1) + eval(e2)
}
MatchError is thrown if no pattern matchces the value of the selector
Forms of patterns
Constructors — e.g. Number(n), Number(_)
Variables
Wildcard patterns _
Constants
Rules:
The same variable name can only appear once in a pattern — Sum(x, x) is an illegal pattern
Variable names begin with a lowercase letter
Names of constants begin with a capital letter (except reserved keywords nulltruefalse)
Lists
Convention: Operators ending in : associate to the right. A :: B :: C is interpreted as A :: (B :: C). They are also seen as method calls of the right-hand operand. So these two are equivalent:
val nums = 1 :: 2 :: 3 :: 4 :: Nil
val nums = Nil.::(4).::(3).::(2).::(1)
// Also equivalent to:
val nums = List(1, 2, 3, 4)
So :: is a prepend operation.
Lists can be pattern-matched:
Nil
p :: ps
x :: Nil
List(p1, p2, p3)
Syntax tips
On constants and variables
You can't pattern-match against a variable in the following way:
def startsWith(list: List[Int], n: Int): Boolean = list match {
case n :: ns => true
case _ => false
}
startsWith(List(1, 2, 3), 1) // true
startsWith(List(1, 2, 3), 4) // true (???)
This is because n is interpreted as a match variable that shadows the parameter n; it is equivalent to any other variable name (e.g. the first case is equivalent to x :: xs). So every non-empty list will be matched. Actually, all names that begin with a lowercase letter are interpreted as match variables (as noted above). You could add an uppercase-beginning constant and match against it (or change the parameter name); but I think this would pollute the code.
The best solution, I think, is wrapping the variable name with backticks ` `. In Scala jargon, this will make it a stable identifier pattern; that is, it will actually match against the value of the variable n:
def startsWith(list: List[Int], n: Int): Boolean = list match {
case `n` :: ns => true
case _ => false
}
startsWith(List(1, 2, 3), 1) // true
startsWith(List(1, 2, 3), 4) // false
Capturing decomposed expressions
Suppose you pattern matched against an expression that decomposed a value, and you want to use the value as a whole in the pattern block:
def foo(list: List[(Char, Int)]): (Char, Int) = list match {
case (c, 1) :: xs => (c, 1)
case _ => ???
}
Here we have repeated the (c, 1) expression in the pattern-block. We can capture it with the @ operator, avoiding a repetition:
def foo(list: List[(Char, Int)]): (Char, Int) = list match {
case (pair @ (c, 1)) :: xs => pair
case _ => ???
}
In this case it is a little more typing, but our intention becomes more explicit and we avoid typing mistakes when copying the LHS expression.
Tuple types:(T1, …, TN) stands for scala.TupleN[T1, …, TN]
Tuple constructors:(e1, …, eN) stands for scala.TupleN(e1, …, eN)
Implicit parameters
Tip: when a method has several parameter lists and one of them is a function value, it is usually advantageous to put the function value last, because then we have a better chance that the types will have been inferred due to the previous parameters.
If we make ord an implicit parameter, we can leave it out in our calls. The compiler will figure it out, looking for a definition that
is marked implicit
has a type compatible with T
either
is visible at the point of the call (this is the case in the calls to msort in the inner merge function); or
is defined in a companion object associated with T (this is the case of Ordering.Int and Ordering.String)
There must be one and only one matching definition. Otherwise it’s an error.
Higher-order operations on lists
map
A simplified implementation of map could be like this:
abstract class List[T] { ...
def map[U](f: T => U): List[U] = this match {
case Nil => this
case x :: xs => f(x) :: xs.map(f)
}
The actual implementation is a little more complicated, because it is tail-recursive and also works for arbitrary collections, not just lists.
(My tail-recursive try:
def map[U](f: T => U): List[U] = {
def mapAcc(xs: List[T], ys: List[U]): List[U] = xs match {
case Nil => ys
case z :: zs => mapAcc(zs, f(z) :: ys)
}
mapAcc(this, Nil)
}
)
filter
abstract class List[T] { ...
def filter(p: T => Boolean): List[T] = this match {
case Nil => this
case x :: xs =>
if (p(x)) x :: xs.filter(p)
else xs.filter(p)
}
filter also has some friends:
filterNot
partition (computes filter and filterNot in one go, returning a pair of Lists)
(m flatMap f) flatMap g == m flatMap (x => f(x) flatMap g)
Left unit
unit(x) flatMap f == f(x)
Right unit
m flatMap unit == m
map
map can be defined as a composition of unit and flatMap:
m map f = m flatMap (x => unit(f(x)))
= m flatMap (f andThen unit)
We can also expand the for single-generator expression as follows:
for (x <- m) yield e1
m.map (x => e1)
m.flatMap (x => unit(e1))
Monad laws and for expressions
Right unit
m
// by right unit law
== m flatMap unit
// `id` is the identity function
== m flatMap (id andThen unit)
// by definition of `map`
== m map id
// by definition of `for` with a single generator
== for (x <- m) yield id(x)
// because `id(x) == x`
== for (x <- m) yield x
or, more simply,
m
// by right unit law
== m flatMap unit
== m flatMap (x => unit(x))
// by our expansion of `for` with `map` defined from `flatMap`
== for (x <- m) yield x
Associativity
LHS:
for (y <- for (x <- m; y <- f(x)) yield y
z <- g(y)) yield z
for (y <- (m.flatMap (x => for (y <- f(x)) yield y))
z <- g(y)) yield z
for (y <- (m.flatMap (x => f(x).map(y => y)))
z <- g(y)) yield z
for (y <- (m.flatMap (x => f(x)))
z <- g(y)) yield z
for (y <- (m flatMap f)
z <- g(y)) yield z
(m flatMap f).flatMap(y => for (z <- g(y)) yield z)
(m flatMap f) flatMap g
RHS:
for (x <- m; y <- f(x); z <- g(y)) yield z
m flatMap (x => for (y <- f(x); z <- g(y)) yield z)
m flatMap (x => f(x).flatMap(y => for (z <- g(y)) yield z))
m flatMap (x => f(x) flatMap g)