# HG changeset patch # User Christian Urban # Date 1670521988 0 # Node ID 4772b61667207368962f1ffe57c366763139d49a # Parent b183e0dfb7ec6294a581641e0574efb362662343 updated diff -r b183e0dfb7ec -r 4772b6166720 main_testing2/wordle_test.sh --- a/main_testing2/wordle_test.sh Fri Dec 02 12:55:59 2022 +0000 +++ b/main_testing2/wordle_test.sh Thu Dec 08 17:53:08 2022 +0000 @@ -133,8 +133,8 @@ echo " score(\"chess\", \"eexss\") == List(P, A, A, C, C)" >> $out echo "" >> $out echo " val p = pool(\"chess\", \"caves\")" >> $out - echo " aux(\"chess\".toList, \"caves\".toList, Nil) == List(P, A, A, A, C)" >> $out - echo " aux(\"chess\".toList, \"caves\".toList, p) == List(P, A, A, P, C)" >> $out + echo " aux(\"chess\".toList, \"caves\".toList, Nil) == List(C, A, A, A, C)" >> $out + echo " aux(\"chess\".toList, \"caves\".toList, p) == List(C, A, A, P, C)" >> $out if (scala_assert "wordle.scala" "wordle_test3b.scala") then diff -r b183e0dfb7ec -r 4772b6166720 wsheets/wsh03.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/wsheets/wsh03.scala Thu Dec 08 17:53:08 2022 +0000 @@ -0,0 +1,78 @@ + +// Task 1 + +abstract class Tree +case class Leaf(x: Int) extends Tree +case class Node(left: Tree, right: Tree) extends Tree + +def mirror(t: Tree) : Tree = t match { + case Leaf(n) => Leaf(n) + case Node(l, r) => Node(mirror(r), mirror(l)) +} + +def sum_tree(t: Tree) : Int = t match { + case Leaf(n) => n + case Node(l, r) => sum_tree(l) + sum_tree(r) +} + +// Task 2 + +// version with default argument +def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = xs match { + case Nil => Nil + case x::xs => if (acc.contains(x)) remdups(xs, acc + x) + else x::remdups(xs, acc + x) +} + +//version with auxiliary function +def remdups(xs: List[Int]) = { + def aux(xs: List[Int], acc: Set[Int]) : List[Int] = xs match { + case Nil => Nil + case x::xs => if (acc.contains(x)) aux(xs, acc + x) + else x::aux(xs, acc + x) + } + aux(xs, Set()) +} + + +// Task 3 +def indexOfOption(xs: List[Int], e: Int) : Option[Int] = xs match { + case Nil => None + case x::xs => if (x == e) Some(0) + else indexOfOption(xs, e).map(_ + 1) +} + +indexOfOption(List(1,2,3,4,5,6), 7) // => None +indexOfOption(List(1,2,3,4,5,6), 4) // => Some(3) +indexOfOption(List(1,2,3,4,3,6), 3) // => Some(2) + + +// Task 4 (Pattern Matching, If-Guards, hard) + +def height(t: Tree) : Int = t match { + case Leaf(_) => 0 + case Node(l, r) => 1 + List(height(l), height(r)).max +} + +def balance(t: Tree) : Tree = t match { + case Leaf(n) => Leaf(n) + case Node(l, r) if (height(l) - height(r)).abs <= 1 + => Node(l, r) + case Node(l, r : Node) if height(l) < height(r) => + balance(Node(Node(l, r.left), r.right)) + case Node(l : Node, r) if height(l) > height(r) => + balance(Node(l.left, Node(l.right, r))) +} + +balance(Node(Leaf(1), Node(Leaf(2), Node(Leaf(3), Leaf(4))))) + +// Task 5 (fold, hard) + +def fold(xs: List[Int], f: (Int, Int) => Int, u: Int) : Int = xs match { + case Nil => u + case x::xs => f(x, fold(xs, f, u)) +} + + +def sum(xs: List[Int]) = fold(xs, _ + _, 0) +def prod(xs: List[Int]) = fold(xs, _ * _, 1) \ No newline at end of file diff -r b183e0dfb7ec -r 4772b6166720 wsheets/wsh04.scala --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/wsheets/wsh04.scala Thu Dec 08 17:53:08 2022 +0000 @@ -0,0 +1,78 @@ + +// Task 1 + +abstract class Tree +case class Leaf(x: Int) extends Tree +case class Node(left: Tree, right: Tree) extends Tree + +def mirror(t: Tree) : Tree = t match { + case Leaf(n) => Leaf(n) + case Node(l, r) => Node(mirror(r), mirror(l)) +} + +def sum_tree(t: Tree) : Int = t match { + case Leaf(n) => n + case Node(l, r) => sum_tree(l) + sum_tree(r) +} + +// Task 2 + +// version with default argument +def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = xs match { + case Nil => Nil + case x::xs => if (acc.contains(x)) remdups(xs, acc + x) + else x::remdups(xs, acc + x) +} + +//version with auxiliary function +def remdups(xs: List[Int]) = { + def aux(xs: List[Int], acc: Set[Int]) : List[Int] = xs match { + case Nil => Nil + case x::xs => if (acc.contains(x)) aux(xs, acc + x) + else x::aux(xs, acc + x) + } + aux(xs, Set()) +} + + +// Task 3 +def indexOfOption(xs: List[Int], e: Int) : Option[Int] = xs match { + case Nil => None + case x::xs => if (x == e) Some(0) + else indexOfOption(xs, e).map(_ + 1) +} + +indexOfOption(List(1,2,3,4,5,6), 7) // => None +indexOfOption(List(1,2,3,4,5,6), 4) // => Some(3) +indexOfOption(List(1,2,3,4,3,6), 3) // => Some(2) + + +// Task 4 (Pattern Matching, If-Guards, hard) + +def height(t: Tree) : Int = t match { + case Leaf(_) => 0 + case Node(l, r) => 1 + List(height(l), height(r)).max +} + +def balance(t: Tree) : Tree = t match { + case Leaf(n) => Leaf(n) + case Node(l, r) if (height(l) - height(r)).abs <= 1 + => Node(l, r) + case Node(l, r : Node) if height(l) < height(r) => + balance(Node(Node(l, r.left), r.right)) + case Node(l : Node, r) if height(l) > height(r) => + balance(Node(l.left, Node(l.right, r))) +} + +balance(Node(Leaf(1), Node(Leaf(2), Node(Leaf(3), Leaf(4))))) + +// Task 5 (fold, hard) + +def fold(xs: List[Int], f: (Int, Int) => Int, u: Int) : Int = xs match { + case Nil => u + case x::xs => f(x, fold(xs, f, u)) +} + + +def sum(xs: List[Int]) = fold(xs, _ + _, 0) +def prod(xs: List[Int]) = fold(xs, _ * _, 1) \ No newline at end of file diff -r b183e0dfb7ec -r 4772b6166720 wsheets/wsh04.tex --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/wsheets/wsh04.tex Thu Dec 08 17:53:08 2022 +0000 @@ -0,0 +1,117 @@ +% !TEX program = xelatex +\documentclass{article} +\usepackage{../styles/style} +\usepackage{../styles/langs} +\usepackage{tikz} +\usepackage{pgf} +\usepackage{marvosym} +\usepackage{boxedminipage} + +\lstset{escapeinside={/*!}{!*/}} +\newcommand{\annotation}[1]{\hfill\footnotesize{}#1} + +\usepackage{menukeys} + + +% Exact colors from NB +\usepackage[breakable]{tcolorbox} +\definecolor{incolor}{HTML}{303F9F} +\definecolor{outcolor}{HTML}{D84315} +\definecolor{cellborder}{HTML}{CFCFCF} +\definecolor{cellbackground}{HTML}{F7F7F7} + + + +\begin{document} +\fnote{\copyright{} Christian Urban, King's College London, 2022} + +\section*{Scala Worksheet 4} + + + +\subsection*{Task 1 (Options Again)} + + + +\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} + +\subsection*{Task 2 (Pattern-Matching, Accumulators)} + +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] +def remdups(xs: List[Int], acc: Set[Int] = Set()) : List[Int] = ??? +\end{lstlisting} + +\noindent +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. + +\subsection*{Task 3 (Pattern-Matching, Options, Maps)} + +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> 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} + +\subsection*{Task 4 (Pattern-Matching, If-guards, hard)} + +Recall the tree definition from Task 1. Define a \texttt{height} +function that calculates the height of a tree. + +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. + +\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 $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$. +% +\[ + \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} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: