Recursion can be stack intensive – depending on the stack size, StackOverFlowErrors may occur.
The Scala compiler can automatically optimize tail recursive operations, i.e. where the recursive call is the last instruction.
Best Practice: When writing recursive methods, ensure they are tail recursive.
If we want to verify that an operation is tail recursive, use the @tailrec annotation.
By default, the Scala compiler applies tail call optimization silently to code that qualifies.
We can introduce an accumulator in order to make our factorial method tail recursive
def factorial(n: Int): BigInt = {
@tailrec
def fact(n: Int, acc: BigInt): BigInt =
if (n == 0) acc else fact(n - 1, n * acc)
fact(n, 1)
}
Here we use a local tail recursive method.
Our exposed factorial method has the expected signature.
2. Partial Function
Scala has a PartialFunction trait that extends Function1 with an isDefinedAt method so that users can test if the function is defined before calling it.
trait PartialFunction[A, B] extends A => B {
def isDefinedAt(a: A): Boolean
def apply(a: A) : B
}
val sqrt = new PartialFunction[Double, Double] {
def isDefinedAt(a: Double) = a >= 0
def apply(a: Double) = scala.math.sqrt(a)
}
List(25.0, -4.0, 9.0).collect(sqrt)
// res25: List[Double] = List(5.0, 3.0)
Collect is similar to map but skips elements where the partial function is not defined.
A partial function literal is given with a block of case alternatives:
val sqrt : PartialFunction[Double, Double] = {
case a if a >= 0 => scala.math.sqrt(a)
}
Such implementations check the match conditions in both isDefinedAt and apply.
3. Currying Methods and Partially Applied Function
Currying is the transformation of a function taking multiple arguments into a chain of functions—each of which take only one.
def spicyAdd(x: Int)(y: Int) = x + y
To invoke a curried method, we must provide values for all argument lists:
spicyAdd(1)(2)
// res0: Int = 3
If we replace one or more of a function's argument lists with the underscore (_), we can convert a function into a partially applied function:
val addOne = spicyAdd(1) _
// addOne: Int => Int = <function1>
addOne(2)
// res0: Int = 3
spicyAdd _
// res1: Int => (Int => Int) = <function1>
Applying only some of the argument lists will return a new function which expects only the missing arguments.
4. Pattern Matching and Extractor Object
Case classes support pattern matching by automatically defining an unapply method in their companion object.
class Name(val first: String, val last: String)
object MyExtractor {
def unapply(name: Name) : Option[(String, String)] =
Some((name.first, name.last))
}
val MyExtractor(a, b) = new Name("John", "Doe")
a: String = John
b: String = Doe
5. Implicit Conversions
When the compiler encounters a type error, rather than giving up it looks for an implicit conversion.
If the actual type doesn't match the expected type, Scala looks for an implicit conversion to the expected type:
2 - "1" // - expects an Integer... got a String
If we try to access a member which doesn't exist, Scala looks for an implicit
conversion of the receiver to something else that has that member: "2" - 1 // String lacks a -(x: Int) method...
In the files in which we're defining implicit methods, we can add an import clause:
import scala.language.implicitConversions
To define an implicit conversion, we declare a method prefixed with the implicit keyword:
implicit def stringToInt(s: String): Int =Integer parseInt s
- While the name of the method doesn't matter, by convention it should be unambiguous and descriptive.
- Idiomatic Convention: Implicit conversions should be named sourceToTarget, e.g. stringToInt
Best Practice: To simplify the use of implicits, we should prefer the placement of implicit conversions inside companion objects.
- No special imports are needed.
- Local overrides are always possible, due to precedence.
6. Custom Value Classes
Normally, all user defined classes in Scala extend AnyRef, with AnyVal (“Value Classes”) reserved for system primitives.
To define a custom Value Class, we must declare a new class which extends AnyVal:
class Weight(val underlying: Double) extends AnyVal {
def +(that: Weight): Weight =
new Weight(this.underlying + that.underlying)
}
There are also some rules we have to follow in defining Value Classes.
- They must accept exactly one class parameter.
- The single class parameter must be promoted to a val.
- There may not be any other fields (val and var) defined in the class.
7. Implicit Classes
Scala 2.10 introduced improved syntax for extension classes, in the form of Implicit Classes. To define one, we prefix a class definition with the keyword implicit:
implicit class IntReverse(val n: Int) extends AnyVal {
def reverse: Int =
n.toString.reverse.toInt
}
123.reverse
// res0: Int = 321
• Similar to Value Classes, Implicit Classes must have exactly one class parameter.
• They must be contained in a package object, singleton, or class – methods cannot be top-level.
In addition to methods and classes, the implicit keyword can be used in method parameter lists:
def pow(x: Double)(implicit y: Double): Double =
math.pow(x, y)
NOTE: The implicit keyword may only be used in the last parameter list of a method.
If implicit arguments are omitted, the Scala compiler will try to resolve them implicitly by looking for implicit values
8. Type Variance
Type Parameters
case class Tuple2[A, B]
trait Set[A] {
def map[B](f: A => B): Set[B]
}
• Classes, traits, and methods can accept type parameters. This is known as parametric polymorphism.
• We accept one or more type parameters, declared and provided in square brackets[ ].
• Idiomatic Convention: Type parameters should be declared as single capital letters, usually
starting with and proceeding in alphabetic order.
Variance and Mutability
val cage: Cage[Animal] = new Cage[Bird] // OK if covariant
cage.put(new Elephant) // Oops!
• At first glance, variance rules result from mutability:
• Read-only (immutable) => Covariant
• Write-only => Contravariant
• Read + Write (mutable) => Invariant
By default, parameterized types are invariant.
val cage: Cage[Animal] = new Cage[Bird]
/*
<console>:10: error: type mismatch;
found : Cage[Bird]
required: Cage[Animal]
Bird <: Animal, but class Cage is invariant in type A.
You may wish to define A as +A instead. (SLS 4.5)
*/
Whether we can declare variance is dependent upon the positions where the type parameter is used.
• Only in covariant positions (immutable) => Covariant
• Only in contravariant positions (write-only) => Contravariant
• Mixed (Read + Write) => Invariant
9. Type Boundaries
Declaring a Lower Bound expresses a relation of “must be a supertype of”. We declare a Lower Bound on a type parameter with the >: modifier:
case class Cage[A >: Animal](animal: A)
Scala will widen the type as much as necessary to meet the boundary:
Cage(new Bird)
// res0: Cage[Animal] = Cage(Bird@653e266e)
Cage("String")
// res1: Cage[Object] = Cage(String)
Cage(1)
// res2: Cage[Any] = Cage(1)
Declaring an Upper Bound expresses a relation of “is a”, and is declared with the <: modifier:
case class Cage[A <: Animal](animal: A)
The type argument is required to be a subtype of the Upper Bound.
10. Type Classes
A type class provides an interface for performing certain operations on various types.
Inheritance often serves a similar role.
• Type Classes can be applied to every type, including final classes.
• They introduce less coupling and more flexibility than inheritance.
• Scala has no language-level support for type classes, but we can use implicits to implement them very flexibly.
A Type Class is a polymorphic trait declaring an interface:
trait Bool[A] {
def isValid(a: A): Boolean
}
A Type Class instance is an implicit value which defines the interface for a given type:
implicit val intBool = new Bool[Int] {
override def isValid(n: Int): Boolean =
n != 0
}
intBool isValid 0
// res0: Boolean = false
11. Tricking Type Erasure
Because the JVM has ‘Type Erasure’, type arguments are never
available at runtime:
def conforms[A](any: Any): Boolean =
any.isInstanceOf[A]
Scala provides some compiler tricks to work around this. We can utilize a ClassTag Context Bound to preserve the type information:
def conforms[A : ClassTag](any: Any): Boolean
• A ClassTag[A] wraps a Class[A] runtime class.
• An implicit ClassTag is created by the compiler as needed.
12. Call By Name
By ‘default’ method parameters are evaluated at the call site.
• Sometimes, however, it makes more sense to defer the evaluation to a later point within the execution of the method. Some examples include:
• Avoiding superfluous (or computationally expensive) evaluations such as in Option.getOrElse()
We use ⇒ in a type annotation to declare a parameter is evaluated by-name: def debug(msg: ⇒ String): Unit =
if (isDebugEnabled()) println(msg)
• By-Name parameters are evaluated every time they are used in the
method.
• Consider the above example; we save CPU cycles by only evaluating the
value of msg if debugging is enabled.
13. Futures
JVMs threads are implemented using native threads. Costly:
• Context switch time
• Memory consumption
Scala Futures provide light weight concurrent tasks running within
a small number of threads (execution contexts).
A Future[A] eventually (or immediately) produces a value of type A or a Throwable.
Future.apply takes an expression (a by-name parameter) and schedules it for evaluation in the thread pool of an ExecutionContext (passed implicitly).
import scala.concurrent.Future
import scala.concurrent.ExecutionContext.Implicits.global
Future(1 to 10000000 sum)
Creating a Future without scheduling a task.
import scala.concurrent.Promise
import scala.util.Success
val promise = Promise[Int]()
promise.future
promise.complete(Success(10))
14. Functor, Applicative and Monad
Functor, Applicative and Monad are important classes that apply to types of kind * => *, such as List, Option and Future .
The classes are progressively more narrow:
Functor >: Applicative >: Monad
Functor has a map method with this signature: (A => B) => F[A] => F[B]
trait Functor[F[_]] {
def map[A, B](f: A => B)(fa: F[A]) : F[B]
}
Roughly speaking, if a type F is a functor, you can apply
functions "inside" F.
Applicative has apply and pure methods with this signature: F[A => B] => F[A] => F[B]
A => F[A]
trait Applicative[F[_]] {
def apply[A, B](f: F[A => B])(fa: F[A]) : F[B]
def pure[A](a: A) : F[A]
}
Roughly speaking, if a type F is an applicative, you can combine multiple
instances of F , merging the values inside each in any way you like.
Monad has flatMap and pure methods with this signature: (A => F[B]) => F[A] => F[B]
A => F[A]
trait Monad[F[_]] {
def flatMap[A, B](f: A => F[B])(fa: F[A]) : F[B]
def pure[A](a: A) : F[A]
}
Roughly speaking, if a type F is a monad, you can combine multiple instances
of F , where some are chosen based on the values located inside the others.
No comments:
Post a Comment