Data Types II PDF

# Chapter 11 Data Types II ## 11.1 Type classes In Python we could implement our sorting algorithms and could use it for any types. This worked since Python is a dynamically typed programming language. For Scala let us consider the insertionsort algorithm for integer numbers: ```scala def insert(...

# Chapter 11 Data Types II ## 11.1 Type classes In Python we could implement our sorting algorithms and could use it for any types. This worked since Python is a dynamically typed programming language. For Scala let us consider the insertionsort algorithm for integer numbers: ```scala def insert(y: Int, list: List[Int]): List[Int] = list match case Nil => List(y) case x::xs if y<=x => y :: list case x::xs => x :: insert(y,xs) def insertionsort(list: List[Int]): List[Int] = list match case Nil => Nil case x::xs => insert(x, insertionsort(xs)) ``` We could now swap the data type Int with an arbitrary type T, making the function polymorphic. Nevertheless, the program would not compile, since the data type T does not necessarily contain elements of a totally ordered universe, i.e., the comparison y<=x might be undefined. This problem can be solved by using type classes and restricting arbitrary types to these type classes. A type class can be seen as a set of types that have some operations in common. In other words, a type class aggregates operations, that each type of the class must implement. We will consider two examples. ## 11.1.1 Type class Ordering The type class Ordering has types whose values can be ordered according to some compare-operation. Most of the known types are instances of Ordering, for example Char, Boolean, String, the number types, and many more. Each type, that is instance of the type class Ordering must implement the following function: ```scala Precondition: None // Effect: None // Result: A negative number is returned, if the first argument is smaller. A positive number is returned, if the first argument is larger. O is returned, if the arguments are equal. def compare(a:T, b:T): Int ``` Once the function is implemented, we can use it in our program, as follows: ```scala >>> Ordering[Double].compare(3.4, 2.3) >>> Ordering[String].compare("Hallo", "Hello") >>> Ordering[Boolean].compare(false, false) //--> +1, 1.2., 3.422.3 //-->-4, 1.e., "Hallo" < "Hello" //--> 0 ``` Finally, we can implement a polymorphic insertionsort algorithm by restricting the type T of elements to the type class Ordering as follows: ```scala Precondition: list is sorted in increasing order. // Effect: None // Result: The list is sorted in increasing order and // contains y and the elements of the input list. def insert[T: Ordering](y: T, list: List[T]): List[T] = list match case Nil => List(y) case x::xs if Ordering[T].compare(y,x) < 0 => y:: list case x::xs => x:: insert(y,xs) // Precondition: None // Effect: None // Result: A copy of the input list, but sorted in increasing order is returned. def insertionsort[T: Ordering](list: List[T]): List[T] = list match case Nil => Nil case x::xs => insert(x, insertionsort(xs)) ``` The restriction is due to the syntax `[T: Ordering]`, we can read this as follows: T is an arbitrary type but contained in the type class Ordering. The operation `compare` in the `insert`-function can only be used since T is of type class Ordering. Moreover, we can skip the precondition that the elements are from a totally ordered universe - this issue is now addressed by the signature of the function. However, it is truly more convenient to use `y < x` instead of the very long statement `Ordering[T].compare(y,x) < 0`. In many cases, Scala gives us the opportunity to import the corresponding syntax. This can be achieved as follows: ```scala def insert[T: Ordering](y: T, list: List[T]): List[T] = val ord = summon[Ordering[T]] import ord.mkOrderingOps list match case Nil => List(y) case x::xs if y<=x => y :: list case x::xs => x:: insert(y,xs) ``` ## 11.1.2 Type class Numeric Another important type class is Numeric. All the classic number data types (including Char) are instances of Numeric. This class enables important operations on numbers like `+`, `-`, or `/` but also different type cast operations. More precisely, a type T is instance of Numeric if it implements the following functions: ```scala def compare(a: T, b: T): Int def fromInt(x: Int): T def minus(x: T, y: T): T def negate(x: T): T def parseString(str: String): Option[T] def plus(x: T, y: T): T def times(x: T, y: T): T def toDouble(x: T): Double def toFloat(x: T): Float def toInt(x: T): Int def toLong(x: T): Long ``` We do not want to discuss the functions and their specifications in detail. Instead, we want to briefly discuss two important issues: - A numeric always have the compare-method. Hence, every numerical type is always considered as instance of type class Ordering. - We might also observe that there is no division-function. This division function for example is defined in another class type, like `Integral` or `Fractional`. Therefore, a pure numerical does not have a way to divide elements. The type classes and their correlations define some kind of hierarchical structure. Our examples might look as follows: Numeric is a subset of Ordering. Integral and Fractional are then subsets of Numeric. The data types Int or Long are elements in the type class Integral, while Double and Float are elements in Fractional. Similar to Ordering we are able to import syntax to use `+` instead of `plus` or `*` instead of `times`. ```scala val num = summon[Numeric[T]] import num.mkNumericOps ``` Later, we discuss how we can build our own data types and implement them as instances of type classes like Ordering or Numeric. ## 11.2 Algebraic Data Types Up to now we only used predefined data types or type aliases like ```scala type Time = (Int, Int, Int) ``` Now, we want to define our own data types. In Scala, we have at least two possibilities to do this: we can use object-oriented programming concepts like classes or traits - we will discuss them in another chapter. Here, we consider algebraic data types - a functional programming concept. An algebraic data type is a completely new type that emerges from the structured combination of other types. A first example is called Direction and represents the four directions on the map. ```scala enum Direction: case N, E, S, W ``` The type `Direction` now has four constructors. In general we access the different variants using the syntax `<Typename>.<Constructor>`. By using `import <Typename>.*` we can avoid the type name. Moreover, pattern matching can be used to access the different variants. Our first example inverts the direction: ```scala // Precondition: None // Effect: None // Result: The opposite direction of the input is returned. def invert(dir: Direction): Direction = import Direction.* dir match case N => S case S => N case E => W case W => E ``` You might have a look into the graph in https://www.scala-lang.org/api/3.3.0/scala/math/Numeric.html. The variants might also have parameters. This example has two constructors: Rectangle and Circle. ```scala enum Shape: case Rectangle(base: Double, height: Double) case Circle(radius: Double) ``` Again, we can use pattern matching on the two variants: ```scala // Precondition: The shapes have non-negative parameters. // Effect: None // Result: The area of the shape is returned. def area(sh: Shape): Double = import Shape.* sh match case Rectangle (b,h) => b * h case Circle (r) => math.Pi * r ``` ## 11.2.1 Polymorphic Algebraic Data Types can be polymorphic. ```scala enum Option[+T]: case None case Some(value: T) ``` This data type is already implemented in Scala. It might be useful, when using functions that sometimes do not return a (correct) value, for example when opening files or when dividing numbers. ```scala // Precondition: None // Effect: None // Result: If b=0, then None is returned, otherwise Some(a/b) is returned. def divide(a: Double, b: Double) : Option[Double]= import Option.* if b == 0 then None else Some(a/b) ``` ## 11.2.2 Recursion Finally, we can also use recursion to define different variants of an algebraic data type. As an example, we want to consider the natural numbers. We recall the important facts: - (i) We say, that 0 is a natural number, it has no predecessor. - (ii) We have an injective function S(-) that assigns to each natural number n its unique successor S(n). We can model this behaviour by using recursively defined algebraic data types. ```scala enum Nat: case Zero case S(pred: Nat) ``` Now, we can represent the number 4 as `S(S(S(S(Zero))))`, for example. Using pattern matching as well as recursion, we can write a function, that converts a Nat-number to an integer. ```scala // Precondition: None // Effect: None // Result: Integer representation of n is returned. def toInt(n: Nat): Int = import Nat.* n match case Zero => 0 case S(p) => 1 + toInt(p) ``` OK, that one is not tail recursive. But this one is: ```scala def toInt_tail(n: Nat): Int = def help(acc: Int, n: Nat): Int = import Nat.* n match case Zero => acc case S(p) => help(1+acc, p) help(0,n) ``` The following function converts from Int to Nat. ```scala // Precondition: n >= 0 // Effect: None // Result: Nat representation of n is returned. import Nat.* def fromInt(n: Int): Nat = n match case 0 => Zero case _ => S(fromInt(n-1)) ``` Finally, we have another two functions: one computes the sum of two `Nat`-numbers and the other one compares whether two `Nat`-numbers are equal. ```scala // Precondition: None // Effect: None // Result: Sum of n and m is returned. def plus(n: Nat, m: Nat): Nat = import Nat.* n match case Zero => m // 0 + m = m, recursion anchor case S(p) => S(plus(p, m)) // (p+1) + m = (p+m) + 1 // Precondition: None // Effect: None // Result: true is returned, iff n == m. def equals(n: Nat, m: Nat): Boolean = import Nat.* (n, m) match case (Zero, Zero) => true case (S(a), S(b)) => equals(a, b) case (_, _) => false ``` ## 11.2.3 Lists As a last example for algebraic data types we want to implement our own linked lists. Hence, let us remember the inductive definition of a list: - Nil is a list and called the empty list and of type List[T]. - If x is an element of type T and xs a list of type List[T], then x::xs is a list of type List[T]. Here, :: is called cons-operator. We can model this behaviour with algebraic data types as follows. Since Nil and List are already predefined objects in Scala, we need different names. Our algebraic data types for lists looks as follows: ```scala enum MyList[+T]: case Empty case Cons(x: T, xs: MyList[T]) ``` The following functions are known from the last chapter but are now implemented by using our own lists. ```scala def length[T](list: MyList[T]): Int = import MyList.* list match case Empty => 0 case Cons(x, xs) => 1 + length(xs) def map[A, B](list: MyList[A], f: A=>B) : MyList[B]= import MyList.* list match case Empty => Empty case Cons(x, xs) => Cons(f(x), map(xs, f)) def concat[T](l1: MyList[T], l2: MyList[T]): MyList[T] = import MyList.* l1 match case Empty => l2 case Cons(x, xs) => Cons(x, concat(xs, l2)) ``` ## 11.3 Instances of type classes Let us come back to our polymorphic implementation of insertionsort. If we want to sort lists whose elements are of the type Nat, we run into the problem that there is no possibility to compare these numbers. Hence, we have to implement Nat as instance of Ordering. To achieve this, we must implement the compare-function. This works as follows: ```scala object Nat: given Ordering[Nat] with // Precondition: None // Effect: None // Result: A negative number is returned, if the first argument is smaller. // A positive number is returned, if the first argument is larger. // 0 is returned, if the arguments are equal. def compare(n: Nat, m: Nat) = (n, m) match case (Zero, Zero) => 0 case (Zero, _) => -1 case (_, Zero) => +1 case (S(a), S(b)) => compare(a,b) ``` Now we are able to sort elements of type Nat. The first line `object Nat:` is necessary. We will not go into detail to explain the semantics yet. We come back to this when talking about the object-oriented programming concepts. Finally, if we want to use the numeric operation we also need to implement the data type Nat as instance of Numeric. To achieve this, we have to add the line `given Numeric[Nat] with` and implement all the functions we mentioned before. Nevertheless, it might not be a good idea to implement Nat as instance of Numeric, because we have to implement the function ```scala def negate(x: Nat): Nat ``` that negates a number. However, it is not clear what the result of `negate(S(0))` would be, since -1 is not a natural number.