--- /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)
+
+}
--- /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)
+
+}
--- 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
}
--- 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
--- 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
Binary file slides/slides03.pdf has changed
--- 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}
Binary file slides/slides04.pdf has changed
--- 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}
--- 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}