# HG changeset patch # User Christian Urban # Date 1669967283 0 # Node ID d67c5f7177a67bcd3e1e1800ab4757ec6719dee8 # Parent db2a3e3287a980dba60ca92acaf1e2b4898339e3 updated diff -r db2a3e3287a9 -r d67c5f7177a6 progs/fact.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/fact.scala Fri Dec 02 07:48:03 2022 +0000 @@ -0,0 +1,6 @@ +object Fact { + +def fact(n: Int): Int = + if (n == 0) 1 else n * fact(n - 1) + +} diff -r db2a3e3287a9 -r d67c5f7177a6 progs/factT.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/progs/factT.scala Fri Dec 02 07:48:03 2022 +0000 @@ -0,0 +1,6 @@ +object FactT { + +def factT(n: Int, acc: Int): Int = + if (n == 0) acc else factT(n - 1, n * acc) + +} diff -r db2a3e3287a9 -r d67c5f7177a6 progs/lecture3.scala --- a/progs/lecture3.scala Fri Nov 25 00:03:15 2022 +0000 +++ b/progs/lecture3.scala Fri Dec 02 07:48:03 2022 +0000 @@ -1,9 +1,18 @@ // Scala Lecture 3 //================= +// - Higher-Order functions // - maps (behind for-comprehensions) + // - Pattern-Matching +def fib(n: Int) : Int = n match { + case 0 => 1 + case 1 => 1 + case n => fib(n - 1) + fib(n - 2) +} + + abstract class Rexp case object ZERO extends Rexp // matches nothing case object ONE extends Rexp // matches the empty string @@ -310,6 +319,7 @@ // Sudoku //======== +// uses Strings for games type Pos = (Int, Int) val emptyValue = '.' @@ -349,8 +359,8 @@ def search(game: String): List[String] = { if (isDone(game)) List(game) else - candidates(game, emptyPosition(game)).par. - map(c => search(update(game, empty(game), c))).toList.flatten + candidates(game, emptyPosition(game)). + map(c => search(update(game, empty(game), c))).flatten } diff -r db2a3e3287a9 -r d67c5f7177a6 progs/lecture4.scala --- a/progs/lecture4.scala Fri Nov 25 00:03:15 2022 +0000 +++ b/progs/lecture4.scala Fri Dec 02 07:48:03 2022 +0000 @@ -7,11 +7,10 @@ import scala.annotation.tailrec -@tailrec def fact(n: BigInt): BigInt = if (n == 0) 1 else n * fact(n - 1) -@tailrec + def factT(n: BigInt, acc: BigInt): BigInt = if (n == 0) acc else factT(n - 1, n * acc) @@ -22,7 +21,6 @@ def foo[A](args: List[A]) = ??? foo(List("1","2","3","4")) -import scala.annotation.tailrec // from knight1.scala diff -r db2a3e3287a9 -r d67c5f7177a6 progs/sudoku.scala --- a/progs/sudoku.scala Fri Nov 25 00:03:15 2022 +0000 +++ b/progs/sudoku.scala Fri Dec 02 07:48:03 2022 +0000 @@ -189,8 +189,6 @@ "....14....3....2...7..........9...3.6.1.............8.2.....1.4....5.6.....7.8...", "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......") -//println("108:\n" ++ pretty(hard_games(108).replaceAll("\\.", " ")) ++ "\n") -//println("109:\n" ++ pretty(hard_games(109).replaceAll("\\.", " ")) ++ "\n") // for measuring time @@ -203,7 +201,7 @@ val total = - (for ((game, i) <- hard_games.zipWithIndex) yield { + (for ((game, i) <- hard_games.zipWithIndex.par) yield { val secs = time_needed(1, search(game)) println(f"${i}%2.0f: ${game} |${secs}%2.3f secs") secs @@ -216,7 +214,9 @@ // 1 single thread version 800 secs +// // 4 cores parallel version on a moderate laptop 400 secs // 8 cores: 290 secs +// 10 cores: 156 secs // 18 cores: 142 secs diff -r db2a3e3287a9 -r d67c5f7177a6 slides/slides03.pdf Binary file slides/slides03.pdf has changed diff -r db2a3e3287a9 -r d67c5f7177a6 slides/slides03.tex --- a/slides/slides03.tex Fri Nov 25 00:03:15 2022 +0000 +++ b/slides/slides03.tex Fri Dec 02 07:48:03 2022 +0000 @@ -394,6 +394,23 @@ %\begin{frame}<1-20> %\end{frame} +\begin{frame}<1-10>[t] + +\end{frame} + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t,fragile] +\frametitle{\mbox{}\hspace{40mm}\textbf{Testing Server}} + +\begin{textblock}{5}(2,6) +\includegraphics[scale=0.35]{../pics/commits.png} +\end{textblock} + +\end{frame} + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + \end{document} diff -r db2a3e3287a9 -r d67c5f7177a6 slides/slides04.pdf Binary file slides/slides04.pdf has changed diff -r db2a3e3287a9 -r d67c5f7177a6 slides/slides04.tex --- a/slides/slides04.tex Fri Nov 25 00:03:15 2022 +0000 +++ b/slides/slides04.tex Fri Dec 02 07:48:03 2022 +0000 @@ -1,8 +1,8 @@ % !TEX program = xelatex -\documentclass[dvipsnames,14pt,t,xelatex]{beamer} -\usepackage{../slides} -\usepackage{../graphics} -\usepackage{../langs} +\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer} +\usepackage{../styles/slides} +\usepackage{../styles/mygraphs} +\usepackage{../styles/langs} %%\usepackage{../data} \usepackage[export]{adjustbox} \usetikzlibrary{shapes} @@ -177,10 +177,11 @@ Email: & christian.urban at kcl.ac.uk\\ %Office: & N\liningnums{7.07} (North Wing, Bush House)\bigskip\\ Slides \& Code: & KEATS\bigskip\\ - %Office Hours: & Thursdays 12:00 -- 14:00\\ - %Additionally: & (for Scala) Tuesdays 10:45 -- 11:45\\ - \multicolumn{2}{c}{\Large\textbf{https://pollev.com/cfltutoratki576}}\\[2cm] - \textcolor{red}{Scala Install Clinic:} & \textcolor{red}{This evening at 17:00 (online)}\\ + + Office Hour: & Fridays 11:00 -- 12:00\\ + Location: & N7.07 (North Wing, Bush House)\bigskip\\ + + Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\ \\ \end{tabular} \end{center} @@ -188,30 +189,30 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Hints in CW} - -\begin{center} -\includegraphics[scale=0.4]{../pics/hints.png} -\end{center} - -\small -\begin{itemize} - \item Scala Library, e.g.~\texttt{span} in \\ - \url{https://www.scala-lang.org/api/current/scala/collection/immutable/List.html} -\end{itemize} -\end{frame} +%\begin{frame}[c] +%\frametitle{Hints in CW} +% +%\begin{center} +%\includegraphics[scale=0.4]{../pics/hints.png} +%\end{center} +% +%\small +%\begin{itemize} +% \item Scala Library, e.g.~\texttt{span} in \\ +% \url{https://www.scala-lang.org/api/current/scala/collection/immutable/List.html} +%\end{itemize} +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{Discussion Forum} +%\begin{frame}[c] +%\frametitle{Discussion Forum} -\begin{center} -\includegraphics[scale=0.38]{/Users/cu/discussion.png} -\end{center} +%\begin{center} +%\includegraphics[scale=0.38]{/Users/cu/discussion.png} +%\end{center} -\end{frame} +%\end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -333,6 +334,26 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c,fragile] +\frametitle{Last Week: Pattern Matching} +\small + +\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=3mm] +def mkeps(r: Rexp) : Val = r match { + case ONE => Empty + case ALT(r1, r2) => ... + case SEQ(r1, r2) => ... + case STAR(r) => ... + case RECD(x, r1) => Rec(x, mkeps(r)) + ... +} +\end{lstlisting} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c,fragile] \frametitle{Reverse Polish Notation} diff -r db2a3e3287a9 -r d67c5f7177a6 wsheets/wsh03.tex --- a/wsheets/wsh03.tex Fri Nov 25 00:03:15 2022 +0000 +++ b/wsheets/wsh03.tex Fri Dec 02 07:48:03 2022 +0000 @@ -29,158 +29,88 @@ -\subsection*{Task 1 (Options)} +\subsection*{Task 1 (Datatypes, Pattern-Matching)} -Get familiar with the return value of functions that can -``go wrong'': +Define the datatype for binary trees where leaves contain an +integer and inner nodes contain only a left and a right child. +Use pattern-matching to define the following functions: + -\begin{lstlisting}[numbers=none] -scala> List(7,2,3,4,5,6).find(_ < 4) -scala> List(5,6,7,8,9).find(_ < 4) -scala> List(5,6,7,8,9).min -scala> List(5,6,7,8,9).minOption -scala> List[Int]().minOption -\end{lstlisting} +\begin{itemize} +\item[(1)] Define a function \texttt{mirror} that takes a tree as argument and returns +the mirror-image of a tree (meaning left- and right-hand side are +exchanged). +\item[(2)] Define a function \texttt{sum\_tree} that sums up all + leaves in a tree. +\end{itemize} -\noindent -Note that there needs to be a type-annotation for \texttt{List()} otherwise -Scala will not know which \texttt{min}-version it should use. +\subsection*{Task 2 (Pattern-Matching, Accumulators)} -\subsection*{Task 2 (Try)} - -The Scala-Idiom \texttt{Try-getOrElse} allows you to conveniently -deal with failure cases. +Define a function \texttt{remdups} that removes duplicates in a list, +say list of integers. This functions should take a list of integers +as argument and returns a list of integers. In order to remove +elements that have already been seen, use an accumulator which can be +a set of of integers (for fast lookup whether an element has already +been seen). The accumulator can be implemented either with an +auxiliary function or with a default argument like \begin{lstlisting}[numbers=none] -scala> Try(Some(List(5,6,7,8,9).min)).getOrElse(None) -scala> Try(Some(List[Int]().min)).getOrElse(None) -\end{lstlisting} - -\noindent -Note that \texttt{Try} needs the library \texttt{scala.util.\_} to be -imported. - - -\begin{lstlisting}[numbers=none] -def safe_div(x: Int, y: Int) : Option[Int] = - Try(Some(x / y)).getOrElse(None) -\end{lstlisting} - -\subsection*{Task 3 (URLs / Files)} - -For simple tasks such as reading webpages and files, Scala provides -convenient functions \texttt{Source.fromURL} and \texttt{Source.fromFile}. -To try them out, you need to import \texttt{io.Source}. - -\begin{lstlisting}[numbers=none] -scala> Source.fromURL(my_url)("ISO-8859-1").mkString -scala> Source.fromFile(my_file)("ISO-8859-1").mkString -\end{lstlisting} - -\noindent -These functions return an iterator, which can be transformed into a String -using \texttt{mkString}. The second argument fixes the character encoding -and should not be omitted. If you are interested in the individual lines -in the file, for example, you can use - -\begin{lstlisting}[numbers=none] -Source.fromFile(my_file)("ISO-8859-1") - .getLines().toList +def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ??? \end{lstlisting} \noindent -If you are after proper error-handling, then you can use Scala's options -as follows - -\begin{lstlisting}[numbers=none] -Try(Some(Source.fromFile("test.txt")("ISO-8859-1") - .mkString)).getOrElse(None) -\end{lstlisting} +Are you familiar with polymorphic types in Scala? If yes, can you +define \texttt{remdups} generically so that it works for any type +of lists. -This can also be written slightly shorter as - -\begin{lstlisting}[numbers=none] -Try(Source.fromFile("test.txt")("ISO-8859-1") - .mkString).toOption -\end{lstlisting} - -\noindent -In case of reading files, there can be an issue with closing -files properly. For this Scala provides \texttt{Using} +\subsection*{Task 3 (Pattern-Matching, Options, Maps)} -\begin{lstlisting}[numbers=none] - Using(Source.fromFile("test.txt")("ISO-8859-1")) - (_.mkString).toOption -\end{lstlisting} - -\noindent -This closes the files automatically after reading, but otherwise -behaves as the code shown above: It gives a \texttt{Some} in the -success case and \texttt{None} in the failure case. However, -\texttt{Using} requires a function as argument for prescribing -of what to do with the file content in the success case. - -\subsection*{Task 4 (Higher-Order Functions)} - -Higher-Order functions means that Scala allows functions to -have functions as arguments and also allows functions to -return functions. Get familiar with the short-hand notation -for simple functions +Remember that the method \texttt{indexOf} returns $-1$ whenever it +cannot find an element in a list. Define a better version of +this function, called \texttt{indexOfOption} that returns in +the failure case \texttt{None} and in the success case +\texttt{Some}$(n)$ where $n$ is the index of the element in the +list. Try to define this function recursively but without an +auxiliary function. For this use a \texttt{map}. \begin{lstlisting}[numbers=none] -scala> List(7,2,3,4,5,6).find(_ < 4) -scala> List(7,2,3,4,5,6).count(_ % 2 == 0) -scala> List(7,2,3,4,5,6).sortWith(_ > _) -scala> List(7,2,3,4,5,6).filter(_ > 4) +scala> indexOfOption(List(1,2,3,4,5,6), 7) // => None +scala> indexOfOption(List(1,2,3,4,5,6), 4) // => Some(3) +scala> indexOfOption(List(1,2,3,4,3,6), 3) // => Some(2) \end{lstlisting} -\noindent -Be aware that this short-hand notation only works for ``smallish'' functions -and that sometimes Scala cannot figure out the types involved without -explicit type annotations. - -\subsection*{Task 5 (Maps)} +\subsection*{Task 4 (Pattern-Matching, If-guards, hard)} -Get familiar with the map-function for lists, sets etc. It is the -quintessential higher-order function and frequently used for transforming -lists. - -\begin{lstlisting}[numbers=none] -scala> List(7,2,3,4,5,6).map(n => n * n) -\end{lstlisting} +Recall the tree definition from Task 1. Define a \texttt{height} +function that calculates the height of a tree. -\noindent -Make also sure you see that Scala's \texttt{for}-comprehensions -are just syntactic sugar for \texttt{map}s. What would this -expression look like as \texttt{for}-comprehension? What are -the advantages of \texttt{for}-comprehensions over \texttt{map}s. - - -\subsection*{Task 6 (Pattern-Matching)} - -Rewrite the following function using pattern-matching +Define a second function \texttt{balance} that makes sure that the +height of a left and right child is balanced (only differ in heights +by maximal of one). Implement this function by balancing trees +stepwise - reorder that the height difference changes by one and then +the balancing is repeated. -\begin{lstlisting}[numbers=none] -def my_map(lst: List[Int], f: Int => Int) : List[Int] = { - if (lst == Nil) Nil - else f(lst.head) :: my_map(lst.tail, f) -} -\end{lstlisting} - -\noindent -Observe that the type of the function is from \texttt{Int}s to -\texttt{Int}s, which is written in Scala as type \texttt{Int => Int}. - - -\subsection*{Task 7 (Fold, Hard)} +\subsection*{Task 5 (Fold, hard)} Implement a function \texttt{fold} for lists of integers. It takes a list of integers as argument as well as a function $f$ and a unit element $u$. -The function is of type \texttt{(Int, Int) => Int} and the unit element -is an integer. The return type of \texttt{fold} is \texttt{Int}. +The function $f$ is of type \texttt{(Int, Int) => Int} and the unit element +is of type \texttt{Int}. The return type of \texttt{fold} is \texttt{Int}. What is \texttt{fold} supposed to do? Well it should fold the function $f$ over the elements of the list and in case of the empty list return the -unit element $u$. +unit element $u$. +% +\[ + \begin{array}{lcl} + \texttt{fold}(Nil, f, u) & \dn & u\\ + \texttt{fold}(x::xs, f, u) & \dn & f(x, \texttt{fold}(xs, f, u))\\ + \end{array}\smallskip +\] + +\noindent +Use \texttt{fold} to define the sum of a list of integers and the +product of a list of integers. Try to use Scala's shorthand notation +\texttt{\_ + \_} and \texttt{\_ * \_} for functions. \end{document}