Scala Intro

Week 3

Week 3: Data and Abstraction

Lecture 3.1: CLass Hierarchies:

Class Hierarchies: CLasses that extend eachother

  • model of evluation changes
    • method calls might depend on runtime type of receiver of a given method –> dynamic binding
    • revisit family writing

Abstract Class

  • Abstract classes can contain members which are missing an implementation
abstract class IntSet { 
    def incl(x: Int): IntSet
    def containes(x: Int): Boolean 
    }
  • IntSet itself cannot be instantiated, must be suplemented by classes that extend it

References for Sets represented as binary trees:

Class Extension

  • implement sets as binary trees
    • a tree for the empty set
    • a tree consisting of an integer and two sub-trees
  • want to maintain invariant, property that rhs values are greater than the node, and LHS values are less than node
  • purely functional, no mutation –> persistent data structures

See code for IntSet here

  • Empty and NonEmpty extend and conform to type IntSet
    • an object of type Empty or NonEmpty can be used wherever an object of type IntSet is required
  • IntSet is the Superclass, EMpty and NonEmpty are the sub classes
  • standard class object is the superclass of any class –> base class

Object Definitions

  • defining EmptySet as an Object rather than a class
  • defines a singleton object
    • cannot create multiple instances of this object with new
    • singelton objects are values

Exercise: Functional Union Method between two IntSets

  • for Empty set, the union of itself with an other set is always the equivalent to the other set
  • for NonEmpty Sets,
    • first split the LHS set into left and right, and take union
      • yields IntSet excluding elem of LHS set
    • take union between (left union right) and other set
    • finally, incl elem from LHS set
  • each subsequent call union is on a set smaller than the previous, so we can safely assume the recursion terminates

dynamic method dispatch model

  • OO languates implement this, meaning code invoked by a method call depends on the runtime type of the object that contains the method
  • similarity between dynamic dispatch of methods to higher-order functions

Lecture 3.2: How Classes are Organized

Packages

  • classes and objects are organized in packages
  • a package clause at top of source file places subsequent classes and objects into the package
package progfun.examples

object Hello()
  • this would place Hello in the package progfun.examples
  • can subsequently refer to Hello by its fully qualified name
    • progfun.examples.Hello
    • to run Hello from cmd line: scala progfun.examples.Hello

Import clause

  • import week3.Rational –> imports all objects from package.module
  • import week3._ –> imports all objects in package
  • import week3.{Rational, Hello} –> imports two objects from week3

Default Imports

  • members of package:
    • scala –> scala.Int, scala.Boolean
    • java.lang –> java.lang.Object
    • scala.Predef –> scala.Predef.assert

Traits

  • A class can only have one superclass –> Single Inheritance
  • many times, there are many classes that a type naturally conforms to and inherits from –> traits
    • like an abstract class
  • objects can inherit from arbitrarily many traits
    • class Square extends Shape with Planar with Movable...
  • Traits can contain fields and concrete methods
    • cannot contain value parameters

Scala Class Hierarchy

  • scala.Any –> superclass of any other classes
    • base type of all types
    • methods such as ==, toString, universal methods
  • scala.AnyVal
    • base type of all primitive types
  • scala.AnyRef
    • base tyepe of all reference types
  • scala.ScalaObject
  • scala.Null
    • subclass of all AnyRef derived classes
    • the type of null is Null
    • incompatible with AnyVal derived classes
// acceptable
val x = null
val y: String = x

// not acceptable
val z: Int = null

  • scala.Nothing
    • bottom of scala type hierarchy
    • subtype of every other type
    • no value of type nothing –> why useful?
      • to signal abnormal termination
      • as an element type of empty collections –> Set[Nothing]

Exceptions

  • throw Exc
    • aborts evaluation with the exception Exc
object scratch { 

    def error(msg: String) = throw new Error(msg)
}
// returns Nothing --> abnormal termination

what is type of following

  • if (true) 1 else false
    • evaluates as AnyVal
  • Why? Expression is ambiguous, technically can evaluate to Int or Boolean
  • Both inherit from AnyVal –> typechecker picks AnyVal as type for expression

Lecture 3.3: Polymorphism

Types: How compiler Sees classes and functions

  • Type parameterization: classes and methods can have types as parameters

Immutable Linked-List

  • fundamental functional data structure
  • two building blocks:
    • Nil: empty list
    • Cons: a cell containing 1) the first element of the list and 2) the reference/pointer to the remainder of the list

Cons-Lists in Scala

  • A list is either
    • an empty list, new Nil
    • a list new Cons(x, xs) consisting of a head elem x and a tail list, xs

Type parameters

  • too narrow to define only lists with Int elements
  • Generalize the definition using a type parameter
    • Type parameters are written in square brackets, [T]

code for Cons-List implementation

Generic Functions

  • Functions can have type parameters
  • here is a function that creates a list consisting of a single elem

def singleton[T](elem: T): Cons[T] = { new Cons[T](elem, new Nil[T]) }

// can then write:

singleton[Int](1)
singleton[Boolean](true)

Type Inference

  • scala compiler can usually deduce the correct type parameters from value arguments of func call
  • could write singleton(true)

Types and Evaluations

  • notice that type parameters are not persisted somwhere in the data structure
  • in fact, type parametrs do not affect evaluation in scala
  • type parameters and arguments removed befor evaluation
    • Type Erasure

Polymorphism

  • func can be applied to args of many types
  • the type can have instances of many types

Two principle forms of polymorphism:

  1. subtyping: instances of a subclass can be passed to a base class

    • List –> Cons, Nill
    • methods that accept class List can accept Nill or Con as well
    • associated with OO
  2. generics: instances of a func or class are created by type parameterization

    • using type parameterization to create List of Ints, Booleans, etc.
    • Associated with FP

Exercise

  • write func nth that takes an integer n and a list and selects the nth element from the list
  • elements numbered from 0
  • if index outside range from 0 up to length of list minus 1, a IndexOutOfBOundsException should be thrown

code for nth val

Assignment Object-oriented representations based on binary trees. Assignment Code

Avatar
Miguel Rivera-Lanas
Data Scientist / Engineer

Currently a Data Scientist/Engineer at a hedge fund. Primarily focused on empirical methods to study quantitative and social effects of disinformation propagation, content moderation systems, and computational social science generally.