Lists and Higher-Order Functions PDF

# Lists and Higher Order Functions ## 10.1 Lists in Scala - In Python we worked with lists quite a lot. - Of course, Scala also have lists but there are several differences we have to know. - First of all, lists in Scala are immutable, i.e., whenever we fixed an element in this list, we cannot rea...

# Lists and Higher Order Functions ## 10.1 Lists in Scala - In Python we worked with lists quite a lot. - Of course, Scala also have lists but there are several differences we have to know. - First of all, lists in Scala are immutable, i.e., whenever we fixed an element in this list, we cannot reassign another element (*There are also mutable lists, but we need to include packages.*). - Since Scala is a statically typed programming language, the elements of the lists have to be of the same type. - In Python lists are arrays, i.e., the elements of a list are exactly next to each other and we can access an element in constant time. - In Scala, lists consist of linked nodes, i.e., each element has a pointer to the next element. - Thus, the elements are not always next to each other in the memory. - When accessing the *i*-th element of such a list, we need time *O(i)* ## Definition of Lists - **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. For a given list *x::xs* we say that *x* is the head and *xs* is the tail of the list. We can build lists by using the cons-operator or by using a constructor method. Here, we can see some examples: ```scala val as: List [Nothing] - Nil val bs: List [Int]12:13:7:: Nil val cs: List (Char)'a': 'b':: Nil val ds: List [Boolean] List(true, false, false) constructor method ``` In some cases, we do not need to give the types of the variables, since Scala can infer the types. Hence, we could also write: ```scala val bs12 13 7: Nil val cs = 'a':: 'b':: Nil val ds List (true, false, false) // constructor method ``` However, giving the type explicitly is good programming style. ## 10.2 List Functions - In this section we want to implement functions for lists. - The inductive definition of lists gives the advantage that we can use pattern matching to implement several cases. - The first function is called *head* and returns the head of a list. - The function *tail* returns the tail of a list. - Both functions' precondition is that the list is not empty. They are implemented as follows: ```scala def head(list List (Any]): Any = list match case Nil => throw Exception() case x:xx there is no head. def tail(list List (Any)): List (Any] = list match case Nil => throw Exception() case x:: х> ха there is no tail. ``` - Here, we used *Any* in the signature of the functions. - The type *Any* is super type of each type. - Hence, we can use the functions for different types like *List[Int]* or *List[Char]* or whatever. - The functions *tail* and *head* are already defined in Scala, but to call these implemented functions, we need another syntax: ```scala List (1,2,3).tail ``` and ```scala List (1,2,3).head. ``` - The reason is that Scala is object-oriented as well. We will discuss these issues in another unit. ### 10.2.1 Polymorphism - Our implementation of the *concat*-function uses *Any* as type of the elements. - However, the result of `::: ` has the type of the input lists. - To achieve this in Scala, we can use polymorphism. - A polymorphic function has a type parameter and can the be used for arbitrary types. ```scala def concat [A] (listi List [A] list2 List[A]) List [A] = listi match case Nil>> list2 case x::xx: concat(xs, list2) ``` Using polymorphism we could also adapt the functions *head* and *tail*. The following recursive function takes the first *n* elements of a list. If a list has less than *n* elements, it returns the complete list. ```scala def take [A] (n Int, list List[A]): List[A] (n,list) match case (0,)> Nil case (n, Nil) => Nil case (n, x::) >: take(n-1,xa) ``` The following recursive function removes the first *n* elements of a list. If a list has less than *n* elements, it returns the empty list. ```scala def drop [A] (n Int, list List[A]) List[A] (n,list) match case (0,)> list case (n, Nil) => Nil case (n, x::xs) > drop(n-1,xs ``` ### 10.2.2 reverse - The following recursive function reverses a given list: ```scala def reverse [A] (list: List (A)) List [A] list match case Nil Mil case x::xs reverse(s): (x::Nil) ``` - The implementation of this function is inefficient, which the following example demonstrates: ```scala reverse(1::2::3::Mil) = reverse (2::3::Mil) ::: (1::Mil) ■(reverse (3::Mil) ::: (2::Mil)) :: (1::Nil) ((reverse(Nil) :: (3::Nil)) ::: (2::Mil)) ::: (1::Mil) (Nil:: (3:11)) :::2::Mil))::: (1::Mil) ((3::Mil)::: (2::Mil))::: (1::Nil) (3::(Nil::: (2::Mil)))::: (1::Nil) -(3::2::Mil) ::: (1::Nil) -(3::((2::Mil)::: (1::Nil))) 3::2:: (Nil (1::Mil)) 3::2::1::Mil ``` - We can also bound its running time as follows: - let *n* be the length of the list and *T(n)* the number of *::-calls* (not the number of *:::-calls*). - Then we have *T(0) = 0* as recursion anchor. - Moreover, since *reverse(xs)* has *n-1* elements we have *T(n)=T(n-1)+n-1*. - This recursive running time function is known from the worst case example of quicksort and hence, solves to *T(n) ∈ O(n²)*. - Nevertheless, we can use tail recursion to implement an efficient method for reversing a list. ```scala def reverse [A] (list List (A)) def step(acc: List[A], list list match case Nil => acc List [A] = List (A)): List [A] case x::xs => step(x::acc, xs) step(Nil, list) // Initial call of the help function ``` - The *step*-function has running time *T(0) = 0* and *T(n)=1+T(n-1)*, which solves to *T(n) = n ∈ O(n)*. - Here is an example computation: ```scala reverse(1::2::3::Mil) step(Nil, 1::2::3::Mil) = step(1::Nil, 2::3::Mil) = step(2::1::Mil, 3::Mil) step(3::2::1::Nil, Nil) ■3::2::1::Mil ``` ## 10.3 Higher Order Functions - In Scala functions are treated as values. - Specifically, functions can be used as input and output values of other functions. - A function that has another function as input or output (or both) is called higher order function. - The following function takes a function *f* as parameter and applies it twice to an input value *x*. ```scala def applyTwice [A] (f: A=>A, X: A): A = f(f(x)) ``` - The first input parameter has type *A->A*, i.e., it is a function that expects a value of type *A* and returns a value of type *A*. - Let us consider the following two functions: ```scala def addOne(x: Int) Intx+1 def negate (x: Boolean): Boolean = !x ``` We can now write a new function as follows: ```scala def addTwo (x: Int) applyTwice (addOne, x) returns +2 def identity(x: Boolean) applyTwice (negate, x) returns I ``` However, for very simple functions the definitions of *addOne* and *negate* are quite long. Scala provides some syntactical sugar that will shorten the definitions. First, we use *val* instead of *def* as follows: ```scala val addOne = (x: Int) => x+1 ``` - The output type is inferred by Scala. - We can still write *applyTwice(addOne, 40)* to obtain 42. - Finally, if we use the *addone* method only once we can also write instead `applyTwice((_: Int)+1, 40)` ### 10.3.1 Drop and take while - Let us consider two more complicated examples. - We remember the functions *take* and *drop*. - This time, instead of a number, we give a function as predicate, i.e., a function of type *A=>Boolean* and then we take or drop elements until the first element does not satisfy the predicate. ```scala def takeWhile [A] (p: A=>Boolean, list: List[A]): List [A] list match case Nil => Nil takeWhile(p,xs) // take z and add more elements // nothing to take case x::xs if p(x) => x case x::xs if !p(x) => Nil // no more elements to take list match case Nil => Nil // nothing to drop def dropWhile [A] (p: A=>Boolean, list: List[A]): List [A] case x::xs if p(x) => dropWhile (p,xs) // drop z and drop more elements case x::xs if !p(x) => list // no more elements to drop ``` ### 10.3.2 filter - One of the most common higher order functions is the function *filter*. - It removes all elements that are not fulfilled by a given predicate and is implemented as follows: ```scala // Precondition: None // Effect: None // Result: A list is returned that contains all elements // of the input list fulfilling the predicate p. def my_filter [A] (p: A=>Boolean, list: List[A]) : List [A] list match case Nil => Nil case (x::xs) if p(x) => x my_filter(p,xs) case (x::xs) if !p(x) => my_filter(p,xs) ``` This function is already implemented in Scala (and many other languages). If we want to use it, we have to call ```scala list.filter(p) List(3,5,2,1,4,6,4).filter((_: Int)%2 == 0) //--> List (2,4,6,4) ``` ### 10.3.3 map - Another common higher order function is the *map*-function. - It applies to each element of the list a given function and is implemented as follows: ```scala // Precondition: None // Effect: None // Result: A list is returned that contains all elements // of the input but applied by the function f. def my_map [A,B] (f: A=>B, list List[A]) : List [B] list match case Nil => Nil case (x::xs) => f(x): my_map(f,xs) ``` This function is already implemented in Scala (and many other languages). If we want to use it, we have to call ```scala list.map(f) List(1,2,3,4,5,6,7).map(x => x*x) //--> List(1,4,9,16,25,36,49) ``` ### 10.3.4 fold - For the last higher order function we want to discuss some examples first to see some given patterns in the program code. - Let us consider the functions *sum* and *prod* that compute the sum/product of a list of numbers. - Implementations might look as follows: ```scala def sum(list: List (Int)): Int = list match case Nil => 0 case (x::xs) => x + sum(xs) def prod(list: List (Int]): Int = list match case Nil => 1 case (x::xs) x * prod(xs) ``` - Next, as another example let us consider a function, that obtains a predicate and returns *true*, iff all elements of the list satisfy the element. - Here is the implementation: ```scala def forAll [A] (p: A=>Boolean, list: List (A)) : Boolean = list match case Nil => true case (x::xs) => p(x) && forAll(p,xs) ``` - If we take a closer look at all three functions we see many similarities: - First of all, if we consider the recursion anchor we observe that each function returns some neutral element *e*: 0 for the sum, 1 for the product and *true* for the allquantifier. Thus, in general the line looks like this: ```scala case Nil e ``` - Moreover, the structure for the recursive call is similar as well. There is some function *f*, that combines the element *x* with the recursive call: there is *a + b* for the sum, *a * b* for the product and *p(a) && b* for the allquantifier. - The recursive call itself has exactly one element less. - Hence, in general the line might look like this: ```scala case x::XS > f(x, recursive_call(xs)) ``` - This leads to a higher order function called *fold right*. The implementation looks as follows: ```scala def foldr [A,B] (f: (A,B)=>B, e: B, list: List (A)) : B = list match case Nil => e case x::xs => f(x, foldr(f,e,xs)) ``` - This polymorphic function can now be used to implement the three functions in a single line each. ```scala def sum(list: List (Int)) : Int = foldr((_: Int)+(_: Int), 0, list) def prod(list: List (Int)) : Int = foldr((_: Int)*(_: Int), 1, list) def forAll [A] (p : A=>Boolean, list: List (A)) : Boolean = foldr(p(_:A) && (_: Boolean), true, list) ``` - The function *fold right* is right-associative. - That means, if *e* is the neutral element and *o* the given function and *[zo, ..., In-1]* the list, then the *fold right* function computes: *… (In-10 (In … (In-10€))).* - Our implementation of the *fold right* function is not tail recursive. However, the *fold left* function is tail-recursive: ```scala def foldl [A,B] (f: (B,A)=>B, e: B, list: List (A)) : B = list match case Nil => e x::xs => foldl (f, f(e,x),xs) ``` - This *fold-function* is left-associative. - That means, if *e* is the neutral element and *o* the given function and *[To,..., In-1]* the list, then the *fold left* function computes: *…(((eo) 1) 2)... In-1)* - Both functions are already implemented in Scala. Their calls look as follows: ```scala list.foldRight (e) (f) List(1,2,3,4). foldRight (0) ((_: Int)+(_: Int)) list.foldLeft(e) (f) List (1,2,3,4). foldLeft(1) ((_: Int)*(_: Int)) ``` **Attention**: Although we gave recursive implementations of the *fold* functions, Scala's implementations are not recursive. They use loops to evaluate the functions. Of course the advantage of loops is that there is no recursion stack that grows with the number of recursive calls. However, we have shown the recursive implementations since they are easier to understand. (*Trust me!*) ## 10.4 List with insertionsort ### 10.4.1 Insertionsort - Let us start with insertionsort. - We remember, that we needed a help function, that sorts an element into a list of already sorted elements. - In the imperative way, started at the right and pushed the element as far to the left as possible. - This was only possible because we used an array where we had direct access to the positions. - This time, we have to start at the front of the list and push the new element to the right until there is a larger element. - However, the specification of the function remains the same except for the change of result and effect. ```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(y: Int, list: List (Int)) : List (Int] list match case Nil => List(y) case x::xs if y <= x <=> y :: list // Next element is not smaller. Stop. case x::xs => X :: insert(y, xs) // Next element is smaller. Go further. ``` - Next, we can use the *insert*-function to implement insertionsort. - The empty list is already sorted (recursion anchor). - In the recursive step, we first sort the tail recursively and then insert the head into the already sorted list. ```scala def insertionsort(list: List (Int)) : List [Int] = list match case Nil => Nil case x::xs => insert(insertionsort(xs), x) ``` - If we now go back to the pattern we found for the *fold* function, we might observe that insertionsort uses a *fold right* approach. - Thus, we can simplify insertionsort as follows: ```scala def insertionsort(list: List (Int)) : List[Int] = list.foldRight (Nil) (insert) ... such a Beauty ```