--- a/progs/lecture3.scala	Wed Nov 23 13:32:01 2016 +0000
+++ b/progs/lecture3.scala	Thu Nov 24 01:44:38 2016 +0000
@@ -1,18 +1,307 @@
-// regular expressions
-// ?? polymorphism
+// Scala Lecture 3
+//=================
+
+
+// One of only two places where I conceded to mutable
+// data structures: The following function generates 
+// new labels
+
+var counter = -1
+
+def fresh(x: String) = {
+  counter += 1
+  x ++ "_" ++ counter.toString()
+}
+
+fresh("x")
+fresh("x")
+
+// this can be avoided, but would have made my code more
+// complicated
+
+
+// Tail recursion
+//================
+
+def my_contains(elem: Int, lst: List[Int]) : Boolean = lst match {
+  case Nil => false
+  case x::xs => 
+    if (x == elem) true else my_contains(elem, xs)
+}
+
+my_contains(4, List(1,2,3))
+my_contains(2, List(1,2,3))
+
+my_contains(1000000, (1 to 1000000).toList)
+my_contains(1000001, (1 to 1000000).toList)
+
+
+//factorial 0.1
+
+def fact(n: Long): Long = 
+  if (n == 0) 1 else n * fact(n - 1)
+
+fact(10000)
+
 
-A function should do one thing, and only one thing.
+def factT(n: BigInt, acc: BigInt): BigInt =
+  if (n == 0) acc else factT(n - 1, n * acc)
+
+
+factT(10000, 1)
+
+// my_contains and factT are tail recursive 
+// you can check this with 
+
+import scala.annotation.tailrec
+
+// and the annotation @tailrec
+
+// for tail-recursive functions the compiler
+// generates a loop-like code, which does not
+// to allocate stack-space in each recursive
+// call; scala can do this only for tail-recursive
+// functions
+
+// consider the following "stupid" version of the
+// coin exchange problem: given some coins and a,
+// total, what is the change can you get
 
-Make your variables immutable, unless there's a good reason not to.
+val coins = List(4,5,6,8,10,13,19,20,21,24,38,39, 40)
+
+def first_positive[B](lst: List[Int], f: Int => Option[B]): Option[B] = lst match {
+  case Nil => None
+  case x::xs => 
+    if (x <= 0) first_positive(xs, f)
+    else {
+      val fx = f(x)
+      if (fx.isDefined) fx else first_positive(xs, f)
+  }
+}
+
+
+def search(total: Int, coins: List[Int], cs: List[Int]): Option[List[Int]] = {
+  if (total < cs.sum) None 
+  else if (cs.sum == total) Some(cs) 
+  else first_positive(coins, (c: Int) => search(total, coins, c::cs))
+}
+
+search(11, coins, Nil)
+search(111, coins, Nil)
+search(111111, coins, Nil)
 
-You can be productive on Day 1, but the language is deep, so as you go
-along you’ll keep learning, and finding newer, better ways to write
-code. Scala will change the way you think about programming (and
-that’s a good thing).
+val junk_coins = List(4,-2,5,6,8,0,10,13,19,20,-3,21,24,38,39, 40)
+search(11, junk_coins, Nil)
+search(111, junk_coins, Nil)
+
+
+import scala.annotation.tailrec
+
+@tailrec
+def asearch(total: Int, coins: List[Int], acc_cs: List[List[Int]]): Option[List[Int]] = acc_cs match {
+  case Nil => None
+  case x::xs => 
+    if (total < x.sum) asearch(total, coins, xs)
+    else if (x.sum == total) Some(x) 
+    else asearch(total, coins, coins.filter(_ > 0).map(_::x) ::: xs)
+}
+
+val start_acc = coins.filter(_ > 0).map(List(_))
+asearch(11, junk_coins, start_acc)
+asearch(111, junk_coins, start_acc)
+asearch(111111, junk_coins, start_acc)
+
+// moral: whenever a recursive function is resource-critical
+// (i.e. works on large recursion depth), then you need to
+// write it in tail-recursive fashion
+
+
+// Polymorphism
+//==============
+
+def length_int_list(lst: List[Int]): Int = lst match {
+  case Nil => 0
+  case x::xs => 1 + length_int_list(xs)
+}
+
+length_int_list(List(1, 2, 3, 4))
+
+
+def length[A](lst: List[A]): Int = lst match {
+  case Nil => 0
+  case x::xs => 1 + length(xs)
+}
+
 
-Of all of Scala’s benefits, what I like best is that it lets you write
-concise, readable code
+def map_int_list(lst: List[Int], f: Int => Int): List[Int] = lst match {
+  case Nil => Nil
+  case x::xs => f(x)::map_int_list(xs, f) 
+}
+
+map_int_list(List(1, 2, 3, 4), square)
+
+
+// Remember?
+def first[A, B](xs: List[A], f: A => Option[B]): Option[B] = ...
+
+
+// polymorphic classes
+//(trees with some content)
+
+abstract class Tree[+A]
+case class Node[A](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A]
+case object Leaf extends Tree[Nothing]
+
+def insert[A](tr: Tree[A], n: A): Tree[A] = tr match {
+  case Leaf => Node(n, Leaf, Leaf)
+  case Node(m, left, right) => 
+    if (n == m) Node(m, left, right) 
+    else if (n < m) Node(m, insert(left, n), right)
+    else Node(m, left, insert(right, n))
+}
+
+
+// the A-type needs to be ordered
+
+abstract class Tree[+A <% Ordered[A]]
+case class Node[A <% Ordered[A]](elem: A, left: Tree[A], right: Tree[A]) extends Tree[A]
+case object Leaf extends Tree[Nothing]
+
+
+def insert[A <% Ordered[A]](tr: Tree[A], n: A): Tree[A] = tr match {
+  case Leaf => Node(n, Leaf, Leaf)
+  case Node(m, left, right) => 
+    if (n == m) Node(m, left, right) 
+    else if (n < m) Node(m, insert(left, n), right)
+    else Node(m, left, insert(right, n))
+}
+
+
+val t1 = Node(4, Node(2, Leaf, Leaf), Node(7, Leaf, Leaf))
+insert(t1, 3)
+
+val t2 = Node('b', Node('a', Leaf, Leaf), Node('f', Leaf, Leaf))
+insert(t2, 'e')
 
 
 
-ScalaTest download page: http://www.scalatest.org/download
+// Regular expressions - the power of DSLs
+//=========================================
+
+
+abstract class Rexp
+case object ZERO extends Rexp
+case object ONE extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
+
+
+// (ab)*
+val r0 = ??
+
+
+// some convenience for typing in regular expressions
+import scala.language.implicitConversions    
+import scala.language.reflectiveCalls 
+
+def charlist2rexp(s: List[Char]): Rexp = s match {
+  case Nil => ONE
+  case c::Nil => CHAR(c)
+  case c::s => SEQ(CHAR(c), charlist2rexp(s))
+}
+implicit def string2rexp(s: String): Rexp = charlist2rexp(s.toList)
+
+
+val r1 = STAR("ab")
+val r2 = STAR("")
+val r3 = STAR(ALT("ab", "ba"))
+
+
+implicit def RexpOps (r: Rexp) = new {
+  def | (s: Rexp) = ALT(r, s)
+  def % = STAR(r)
+  def ~ (s: Rexp) = SEQ(r, s)
+}
+
+implicit def stringOps (s: String) = new {
+  def | (r: Rexp) = ALT(s, r)
+  def | (r: String) = ALT(s, r)
+  def % = STAR(s)
+  def ~ (r: Rexp) = SEQ(s, r)
+  def ~ (r: String) = SEQ(s, r)
+}
+
+val digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
+val sign = "+" | "-" | ""
+val number = sign ~ digit ~ digit.% 
+
+
+
+// Lazyness with style
+//=====================
+
+// The concept of lazy evaluation doesn’t really exist in 
+// non-functional languages, but it is pretty easy to grasp. 
+// Consider first 
+
+def square(x: Int) = x * x
+
+square(42 + 8)
+
+// this is called strict evaluation
+
+
+def expensiveOperation(n: BigInt): Boolean = expensiveOperation(n + 1) 
+val a = "foo"
+val b = "foo"
+
+val test = if ((a == b) || expensiveOperation(0)) true else false
+
+// this is called lazy evaluation
+// you delay compuation until it is really 
+// needed; once calculated though, does not 
+// need to be re-calculated
+
+// a useful example is
+def time_needed[T](i: Int, code: => T) = {
+  val start = System.nanoTime()
+  for (j <- 1 to i) code
+  val end = System.nanoTime()
+  ((end - start) / i / 1.0e9) + " secs"
+}
+
+
+// streams (I do not care how many)
+// primes: 2, 3, 5, 7, 9, 11, 13 ....
+
+def generatePrimes (s: Stream[Int]): Stream[Int] =
+  s.head #:: generatePrimes(s.tail filter (_ % s.head != 0))
+
+val primes: Stream[Int] = generatePrimes(Stream.from(2))
+
+primes.filter(_ > 100).take(2000).toList
+
+time_needed(1, primes.filter(_ > 100).take(2000).toList)
+time_needed(1, primes.filter(_ > 100).take(2000).toList)
+
+
+
+// streams are useful for implementing search problems ;o)
+
+
+
+
+// The End
+//=========
+
+// A function should do one thing, and only one thing.
+
+// Make your variables immutable, unless there's a good 
+// reason not to.
+
+// You can be productive on Day 1, but the language is deep.
+
+// I like best about Scala that it lets you write
+// concise, readable code

Binary file slides/slides03.pdf has changed

--- a/slides/slides03.tex	Wed Nov 23 13:32:01 2016 +0000
+++ b/slides/slides03.tex	Thu Nov 24 01:44:38 2016 +0000
@@ -3,6 +3,7 @@
 \usepackage{../graphics}
 \usepackage{../langs}
 %\usepackage{../data}
+\usepackage[export]{adjustbox}
 
 \hfuzz=220pt 
 
@@ -18,7 +19,7 @@
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}     
 
 % beamer stuff 
-\renewcommand{\slidecaption}{PEP (Scala) 02, King's College London}
+\renewcommand{\slidecaption}{PEP (Scala) 03, King's College London}
 
 
 \begin{document}
@@ -28,7 +29,7 @@
 \frametitle{%
   \begin{tabular}{@ {}c@ {}}
   \\[5mm]
-  \huge PEP Scala (2) 
+  \huge PEP Scala (3) 
   \end{tabular}}
 
   \normalsize
@@ -44,50 +45,171 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Why Scala?\end{tabular}}
-
+\begin{frame}[c, fragile]
+\frametitle{The Joy of Immutability}
 
 \begin{itemize}
-\item \large {\bf You can avoid \textcolor{blue}{\texttt{null}}}:
-\end{itemize}
-
+\item If you need to manipulate some data in a list say, then you make
+  a new list with the updated values, rather than revise the original
+  list. Easy!\medskip
 
-\begin{textblock}{6}(1,5)
-  \begin{bubble}[10.5cm]\small
-      ``I call it my billion-dollar mistake. It was the invention of
-      the null reference in 1965. At that time, I was designing the
-      first comprehensive type system for references in an object
-      oriented language (ALGOL W). My goal was to ensure that all use
-      of references should be absolutely safe, with checking performed
-      automatically by the compiler. But I couldn't resist the
-      temptation to put in a null reference, simply because it was so
-      easy to implement. This has led to innumerable errors,
-      vulnerabilities, and system crashes, which have probably caused
-      a billion dollars of pain and damage in the last forty years.''
-      \hfill Sir Tony (Hoare)
-\end{bubble}
-\end{textblock}
+  {\small
+  \begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+    val old_list = List(1, 2, 3, 5)
+    val new_list = 0 :: old_list
+  \end{lstlisting}}  
   
-\begin{textblock}{5}(11.8,1)
-\includegraphics[scale=0.20]{hoare.jpg}\\
-\end{textblock}
-  
+\item You do not have to be defensive about who can access the data
+  (concurrency, lazyness).
+\end{itemize}  
 \end{frame}
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\huge\textbf{\texttt{return}}}
+\begin{frame}[t]
+\frametitle{Email: Hate 'val'}
+
+\mbox{}\\[-25mm]\mbox{}
+
+\begin{center}
+  \begin{bubble}[10.5cm]
+  Subject: \textbf{Hate '\textbf{\texttt{val}}'}\hfill 01:00 AM\medskip\\
+
+  Hello Mr Urban,\medskip\\
+
+  I just wanted to ask, how are we suppose to work
+  with the completely useless \textbf{\texttt{val}}, that can’t be changed ever? Why is
+  this rule active at all? I’ve spent 4 hours not thinking on the
+  coursework, but how to bypass this annoying rule. What’s the whole
+  point of all these coursework, when we can’t use everything Scala
+  gives us?!?\medskip\\
 
-\begin{center}\LARGE
-you should never use it
+  Regards.\\
+  \mbox{}\hspace{5mm}\textcolor{black!50}{<<deleted>>}\\
+  \end{bubble}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\mbox{}\\[-25mm]\mbox{}
+
+\begin{center}
+  \begin{bubble}[10.5cm]
+  Subject: \textbf{Re: Hate '\textbf{\texttt{val}}'}\hfill 01:02 AM\bigskip\bigskip\\
+
+  \textcolor{black!70}{
+    \textit{\large<<my usual rant about fp\ldots\\ concurrency bla bla\ldots{} better programs
+    yada>>}}\bigskip\bigskip\bigskip
+  
+  PS: What are you trying to do where you desperately want to use \texttt{var}?
+  \end{bubble}
 \end{center}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c,fragile]
+
+\begin{textblock}{6}(0.5,0.5)
+\begin{bubble}[11.5cm]
+  \small  
+  Subject: \textbf{Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:04 AM\medskip\\
+
+  \textbf{Right now my is\_legal function works fine:}
+  
+\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+ def is_legal(dim: Int, path: Path)(x: Pos): Boolean = {
+   var boolReturn = false
+   if(x._1 > dim || x._2 > dim || x._1 < 0 || x._2 < 0) {
+   else { var breakLoop = false
+          if(path == Nil) { boolReturn = true }
+          else { for(i <- 0 until path.length) {
+                    if(breakLoop == false) {
+                      if(path(i) == x) {
+                        boolReturn = true
+                        breakLoop = true
+                      }
+                      else { boolReturn = false }
+                    } else breakLoop
+            }
+          }
+          boolReturn
+   }
+\end{lstlisting}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(8.2,11.8)
+\begin{bubble}[5.5cm]\footnotesize\bf
+\ldots{}but I can’t make it work with boolReturn being val. What approach would
+you recommend in this case, and is using var in this case justified?
+\end{bubble}
+\end{textblock}
+
+\only<2>{
+\begin{textblock}{6}(0.3,11.8)
+  \begin{bubble}[3.1cm]
+    \textbf{Me:} \includegraphics[scale=0.08, valign=t]{../pics/throwup.jpg}
+  \end{bubble}
+\end{textblock}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+
+\mbox{}\\[-25mm]\mbox{}
+
+\begin{textblock}{6}(0.5,2)
+  \begin{bubble}[11.5cm]
+  Subject: \textbf{Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 01:06 AM\bigskip\\
+  \small
+  
+  OK. So you want to make sure that the \texttt{x}-position is not outside the
+  board....and furthermore you want to make sure that the \texttt{x}-position
+  is not yet in the path list. How about something like\bigskip
+
+\footnotesize\begin{lstlisting}[language=Scala, numbers=none, xleftmargin=-1mm]
+ def is_legal(dim: Int, path: Path)(x: Pos): Boolean = 
+ ...<<some board conditions>>... && !path.contains(x)
+\end{lstlisting}\bigskip
+  
+  \small Does not even contain a \texttt{val}.
+  \end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(7,12)
+\footnotesize\textcolor{black!50}{(This is all on one line)}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t,fragile]
+
+\mbox{}\\[-15mm]\mbox{}
+
+\begin{textblock}{6}(1,3)
+  \begin{bubble}[10.5cm]
+    Subject: \textbf{Re: Re: Re: Re: Hate '\textbf{\texttt{val}}'}\hfill 11:02 AM\bigskip\bigskip\\
+    
+    THANK YOU! You made me change my coding perspective. Because of you,
+    I figured out the next one\ldots
+  \end{bubble}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Types}
 
@@ -122,11 +244,32 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
+
+\begin{frame}[t]
+\frametitle{Where to go on from here?}
+
+\begin{itemize}
+\item Martin Odersky (EPFL)\ldots he is currently throwing out everything
+  and starts again with the dotty compiler for Scala\medskip
+
+\item Elm (\url{http://elm-lang.org})\ldots web applications with style\medskip   
+
+\item Haskell, Ocaml, Standard ML, Scheme 
+\end{itemize}  
+\end{frame}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}\\[3cm]\alert{Questions?}\end{tabular}}
 
-\mbox{}
+\mbox{}\footnotesize
+Thanks: ``\it{}By the way -  Scala is really getting quite fun
+when you start to get the hang of it\ldots''
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 \end{document}