38 %explain graph coloring program (examples from)

    38 %explain graph colouring program (examples from)

   389 Welcome to Scala 2.13.0 (Java HotSpot(TM) 64-Bit Server VM, Java 9).

   389 Welcome to Scala 2.13.1 (Java HotSpot(TM) 64-Bit Server VM, Java 9).

   612 Note that Scala does not have a \code{then}-keyword in an \code{if}-statement.

   612 Note that Scala does not have a \code{then}-keyword in an

   613 Note also that there are a few other ways of how to define a function. We 

   613 \code{if}-statement; and there should be always an \code{else}-branch.

   614 will see some of them in the next sections.

   614 Never write an \code{if} without an \code{else}, unless you know what

   615 you are doing! Note also that there are a few other ways of how to

   616 define a function. We will see some of them in the next sections.

   839 \noindent This is the correct result for sets, as there are

   841 \noindent This\footnote{This returns actually \code{HashSet(2, 1, 3)},

   840 only three equivalence classes of integers modulo 3. Note that

   842 but this is just an implementation detail of how sets are implemented in

   841 in this example we need to ``help'' Scala to transform the

   843 Scala.} is the correct result for sets, as there are only three

   842 numbers into a set of integers by explicitly annotating the

   844 equivalence classes of integers modulo 3. Note that in this example we

   843 type \code{Int}. Since maps and for-comprehensions are

   845 need to ``help'' Scala to transform the numbers into a set of integers

   844 just syntactic variants of each other, the latter can also be

   846 by explicitly annotating the type \code{Int}. Since maps and

   845 written as

   847 for-comprehensions are just syntactic variants of each other, the latter

   848 can also be written as

   903 While hopefully this all about maps looks reasonable, there is one

   906 While hopefully all this about maps looks reasonable, there is one

   935 \noindent In this code I use a variable assignment (\code{val

   938 \noindent In this code I use a value assignment (\code{val

   989 permitted in PEP. It uses a \code{var} and therefore violates the

   992 permitted in PEP. If you submit this kind of code, you get 0 marks. The

   990 immutability property I ask for in your code. Sorry!

   993 code uses a \code{var} and therefore violates the immutability property

   994 I ask for in your code. Sorry!

  1011 TBD

  1014 Functions obviously play a central role in functional programming. Two simple

  1015 examples are

  1016 

  1017 \begin{lstlisting}[numbers=none]

  1018 def even(x: Int) : Boolean = x % 2 == 0

  1019 def odd(x: Int) : Boolean = x % 2 == 1

  1020 \end{lstlisting} 

  1021 

  1022 \noindent

  1023 More interestingly, the concept of functions is really pushed to the

  1024 limit in functional programming. Functions can take other functions as

  1025 arguments and can return a function as a result. This is actually

  1026 quite important for making code generic. Assume a list of 10 elements:

  1027 

  1028 \begin{lstlisting}[numbers=none]

  1029 val lst = (1 to 10).toList  

  1030 \end{lstlisting} 

  1031 

  1032 \noindent 

  1033 Say, we want to filter out all even numbers. For this we can use 

  1034 

  1035 \begin{lstlisting}[numbers=none]

  1036 scala> lst.filter(even)

  1037 List(2, 4, 6, 8, 10)

  1038 \end{lstlisting} 

  1039 

  1040 \noindent

  1041 where \code{filter} expects a function as argument specifying which

  1042 elements of the list should be kept and which should be left out. By

  1043 allowing \code{filter} to take a function as argument, we can also

  1044 easily filter out odd numbers as well.

  1045 

  1046 \begin{lstlisting}[numbers=none]

  1047 scala> lst.filter(odd)

  1048 List(1, 3, 5, 7, 9)

  1049 \end{lstlisting} 

  1050 

  1051 \noindent

  1052 Such function arguments are quite frequently used for ``generic'' functions.

  1053 For example it is easy to count odd elements in a list or find the first

  1054 even number in a list:

  1055 

  1056 \begin{lstlisting}[numbers=none]

  1057 scala> lst.count(odd)

  1058 5

  1059 scala> lst.find(even)

  1060 Some(2)

  1061 \end{lstlisting} 

  1062 

  1063 \noindent

  1064 Recall that the return type of \code{even} and \code{odd} are booleans.

  1065 Such function are sometimes called predicates, because they determine

  1066 what should be true for an element and what false, and then performing

  1067 some operation according to this boolean. Such predicates are quite useful. 

  1068 Say you want to sort the \code{lst}-list in ascending and descending order. 

  1069 For this you can write

  1070 

  1071 \begin{lstlisting}[numbers=none]

  1072 lst.sortWith(_ < _)

  1073 lst.sortWith(_ > _)

  1074 \end{lstlisting} 

  1075 

  1076 \noindent where \code{sortWith} expects a predicate as argument. The

  1077 construction \code{_ < _} stands for a function that takes two arguments

  1078 and returns true when the first one is smaller than the second. You can

  1079 think of this as elegant shorthand notation for 

  1080 

  1081 \begin{lstlisting}[numbers=none]

  1082 def smaller(x: Int, y: Int) : Boolean = x < y

  1083 lst.sortWith(smaller)

  1084 \end{lstlisting} 

  1085 

  1086 \noindent

  1087 Say you want to find in \code{lst} the first odd number greater than 2.

  1088 For this you need to write a function that specifies exactly this

  1089 condition. To do this you can use a slight variant of the shorthand

  1090 notation above

  1091 

  1092 \begin{lstlisting}[numbers=none]

  1093 scala> lst.find(n => odd(n) && n > 2)

  1094 Some(3)

  1095 \end{lstlisting} 

  1096 

  1097 \noindent

  1098 Here \code{n => ...} specifies a function that takes \code{n} as

  1099 argument and uses this argument in whatever comes after the double

  1100 arrow. If you want to use this mechanism for looking for an element that

  1101 is both even and odd, then of course you out of luck.

  1102 

  1103 \begin{lstlisting}[numbers=none]

  1104 scala> lst.find(n => odd(n) && even(n))

  1105 None

  1106 \end{lstlisting} 

  1107 

  1108 While functions taking functions as arguments seems a rather useful

  1109 feature, the utility of returning a function might not be so clear. 

  1110 I admit the following example is a bit contrived, but believe me

  1111 sometims functions produce other functions in a very meaningful way.

  1112 Say we want to generate functions according to strings, as in

  1113 

  1114 \begin{lstlisting}[numbers=none]

  1115 def mkfn(s: String) : (Int => Boolean) =

  1116   if (s == "even") even else odd

  1117 \end{lstlisting}

  1118 

  1119 \noindent

  1120 With this we can generate the required function for \code{filter}

  1121 according to a string:

  1122 

  1123 \begin{lstlisting}[numbers=none]

  1124 scala> lst.filter(mkfn("even"))

  1125 List(2, 4, 6, 8, 10)

  1126 scala> lst.filter(mkfn("foo"))

  1127 List(1, 3, 5, 7, 9)

  1128 \end{lstlisting}

  1129 

  1130 \noindent

  1131 As said, this is example is a bit contrived---I was not able to think

  1132 of anything simple, but for example in the Compiler module next year I

  1133 show a compilation functions that needs to generate functions as

  1134 intermediate result. Anyway, notice the interesting type we had to

  1135 annotate to \code{mkfn}. Types of Scala are described next.

  1136 

  1059 def quo_rem(m: Int, n: Int) : (Int, Int) = (m / n, m % n)

  1184 def quo_rem(m: Int, n: Int) : (Int, Int) =

  1060 \end{lstlisting}

  1185   (m / n, m % n)

  1061 

  1186 \end{lstlisting}

  1075 \code{=>}. For example, the type \code{Int => String} is for a function

  1201 \code{=>}. This is sometimes also called \emph{function arrow}.  For

  1076 that takes an integer as input argument and produces a string as result.

  1202 example, the type \code{Int => String} is for a function that takes an

  1077 A function of this type is for instance

  1203 integer as input argument and produces a string as result.  A function

  1204 of this type is for instance

  1089 string. 

  1216 string. The type of the function generated in \code{mkfn} above, is

  1217 \code{Int => Boolean}.

  1163 input argument. Above you already seen \code{map} and

  1291 input argument. Above you have already seen \code{map} and

  1164 \code{foreach} which need this. Consider the functions

  1292 \code{foreach} which need this feature. Consider the functions

  1196 There is one more type constructor that is rather special. It

  1324 There is one more type constructor that is rather special. It is

  1197 is called \code{Unit}. Recall that \code{Boolean} has two

  1325 called \code{Unit}. Recall that \code{Boolean} has two values, namely

  1198 values, namely \code{true} and \code{false}. This can be used,

  1326 \code{true} and \code{false}. This can be used, for example, to test

  1199 for example, to test something and decide whether the test

  1327 something and decide whether the test succeeds or not. In contrast the

  1200 succeeds or not. In contrast the type \code{Unit} has only a

  1328 type \code{Unit} has only a single value, written \code{()}. This

  1201 single value, written \code{()}. This seems like a completely

  1329 seems like a completely useless type and return value for a function,

  1202 useless type and return value for a function, but is actually

  1330 but is actually quite useful. It indicates when the function does not

  1203 quite useful. It indicates when the function does not return

  1331 return any result. The purpose of these functions is to cause

  1204 any result. The purpose of these functions is to cause

  1332 something being written on the screen or written into a file, for

  1205 something being written on the screen or written into a file,

  1333 example. This is what is called they cause a \emph{side-effect}, for

  1206 for example. This is what is called they cause some effect on 

  1334 example new content displayed on the screen or some new data in a

  1207 the side, namely a new content displayed on the screen or some

  1335 file. Scala uses the \code{Unit} type to indicate that a function does

  1208 new data in a file. Scala uses the \code{Unit} type to indicate

  1336 not have a result, but potentially causes a side-effect. Typical

  1209 that a function does not have a result, but potentially causes

  1337 examples are the printing functions, like \code{print}.

  1210 some side-effect. Typical examples are the printing functions, 

  1338 

  1211 like \code{print}.

  1339 

  1212 

  1340 %%\subsection*{User-Defined Types}

  1213 \subsection*{User-Defined Types}