Worksheet Algebraic Data Types and Pattern Matching

def maximum (xs:List[Int]) : Option[Int] = {
  ...
}

def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = {
  ...
}

def oneFind (xs:List[String], s:String) : Option[String] = {
  xs.find ((x:String) => (x.length > s.length) && x.contains (s))
}

def twoFind (xs:List[String], s:String) : Option[String] = {
  ...
}

public class CountingValues {
  static class Node {
    int item;
    Node next;

    public Node (int item, Node next) { 
      this.item = item; 
      this.next = next; 
    }
  }

  static int count (Node data, int low, int high) {
    int result = 0;
    while (data != null) {
      if (low <= data.item && data.item <= high) {
        result = result + 1;
      }
      data = data.next;
    }
    return result;
  }

  public static void main (String[] args) {
    Node data = null;
    for (int i = args.length - 1; i >= 0; i--) {
      data = new Node (Integer.parseInt (args[i]), data);
    }

    System.out.printf ("count (..., 5, 10) = %d%n", count (data, 5, 10));
  }
}

/* The Scala library includes many other functions on lists that are common.
 * Below we define our own versions of these functions for pedagogical purposes,
 * but normally the library versions would be used instead.
 */

def append [X] (xs:List[X], ys:List[X]) : List[X] =
  xs match
    case Nil   => ys
    case z::zs => z :: append (zs, ys)

def flatten [X] (xss:List[List[X]]) : List[X] =
  xss match
    case Nil     => Nil
    case ys::yss => ys ::: flatten (yss)

/* The "take" function takes the first n elements of a list. */
def take [X] (n:Int, xs:List[X]) : List[X] =
  if n <= 0 then
    Nil
  else
    xs match
      case Nil   => Nil
      case y::ys => y :: take (n - 1, ys)

/* The "drop" function drop the first n elements of a list. */
def drop [X] (n:Int, xs:List[X]) : List[X] =
  if n <= 0 then
    xs
  else 
    xs match
      case Nil   => Nil
      case y::ys => drop (n - 1, ys)

val sampleList : List[Int] = (1 to 12).toList
val takeresult : List[Int] = take (3, sampleList)
val dropresult : List[Int] = drop (3, sampleList)

/* Reverse a list.  This version is straightforward, but inefficient.  Revisited later on. */
def reverse [X] (xs:List[X]) : List[X] =
  xs match
    case Nil   => Nil
    case y::ys => reverse (ys) ::: List (y)

/* zip takes two lists and creates a single list containing pairs from the two lists
 * that occur at the same position.  The definition shows more sophisticated pattern
 * matching: the use of wildcards; overlapping patterns; and decomposing pairs and
 * lists simultaneously.  Note that the "xs" and "ys" in the third case shadow the
 * "xs" and "ys" parameters to the function.
 */
def zip [X,Y] (xs:List[X], ys:List[Y]) : List[(X,Y)] = (xs, ys) match
  case (Nil, _)       => Nil
  case (_, Nil)       => Nil
  case (x::xs, y::ys) => (x, y) :: zip (xs, ys)

val ziplist = zip (List (1, 2, 3), List ("the", "rain", "in", "spain"))

/* unzip decomposes a list of pairs into a pair of lists.
 * The recursive case illustrates pattern-matching the result of the
 * recursive call in order to apply an operation to the elements.
 */
def unzip [X,Y] (ps:List[(X,Y)]) : (List[X], List[Y]) =
  ps match
    case Nil        => (Nil, Nil)
    case (x, y)::qs => 
      val (xs, ys) = unzip (qs)
      (x :: xs, y :: ys)

val unziplist = unzip (ziplist)

def reverse2 [X] (xs:List[X]) : List[X] =
  def aux (xs:List[X], result:List[X]) : List[X] = xs match
    case Nil   => result
    case y::ys => aux (ys, y :: result)

  aux (xs, Nil)

def repeat [X] (x:X, n:Int) : List[X] = {
  if n == 0 then 
    Nil
  else 
    x :: repeat (x, n - 1)
}

val xs:List[(Char,Int)] = List (('a', 2), ('b', 4), ('c', 8))

val ys = xs.map ((p:(Char,Int)) => repeat (p._1, p._2))

val zs = xs.flatMap ((p:(Char,Int)) => repeat (p._1, p._2))

class Counter {
  private static int numCounters = 0;

  final int id;
  int count;

  Counter (int initial) {
    this.id = numCounters;
    this.count = initial;
    numCounters++;
  }

  static int getNumCounters () {
    return numCounters;
  }

  int getId () {
    return this.id;
  }

  int getNextCount () {
    return this.count++;
  }
}

enum MyList[+X] {
  ...
}
import MyList._

  def length [X] (xs:MyList[X]) : Int = {
    ...
  }

  def toList [X] (xs:MyList[X]) : List[X] = {
    ...
  }

  def fromList [X] (xs:List[X]) : MyList[X] = {
    ...
  }

  def append [X] (xs:MyList[X], ys:MyList[X]) : MyList[X] = {
    ...
  }

  def map [X,Y] (xs:MyList[X], f:X=>Y) : MyList[Y] = {
    ...
  }

enum Tree[+X] {
  case Leaf
  case Node(l:Tree[X], c:X, r:Tree[X])
}
import Tree.{Leaf,Node}

val tree1:Tree[Int] = Leaf

val tree2:Tree[Int] = Node (Leaf, 5, Leaf)

val tree3:Tree[Int] = Node (Node (Leaf, 2, Leaf), 3, Node (Leaf, 4, Leaf))

// Find the size of a binary tree.  Leaves have size zero here.
def size [X] (t:Tree[X]) : Int = {
  ...
}

// Insert a number into a sorted binary tree.
def insert [X] (x:X, t:Tree[X], lt:(X,X)=>Boolean) : Tree[X] = {
  ...
}

// Put the elements of the tree into a list using an in-order traversal.
def inorder [X] (t:Tree[X]) : List[X] = {
  ...
}

def maximum (xs:List[Int]) : Option[Int] = {
  xs match {
    case Nil   => None
    case y::ys => 
      maximum (ys) match {
        case None => Some (y)
        case Some (z) => Some (y max z)
      }
  }
}

 maximum (List(11,31,21))
=> maximum (List(31,21)) match [with y=11] { ... }
=> (maximum (List(21)) match [with y=31] {...}) match [with y=11] { ... }
=> ((maximum (List()) match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... }
=> ((None match [with y=21] {...}) match [with y=31] {...}) match [with y=11] { ... }
=> (Some(21) match [with y=31] {...}) match [with y=11] { ... }
=> Some(31 max 21) match [with y=11] { ... }
=> Some(31) match [with y=11] { ... }
=> Some(11 max 31)
=> Some(31)

 maximum(List())
=> None

maximum(List(21))
=> maximum(List()) match {...}
=> None match {...}
=> Some(21)

maximum(List(31,21))
=> maximum(List(21)) match {...}
=> Some(21) match {...}
=> Some(31 max 21)
=> Some(31)

maximum(List(11,31,21))
=> maximum(List(31,21)) match {...}
=> Some(31) match {...}
=> Some(11 max 31)
=> Some(31)

def maximum (xs:List[Int]) : Option[Int] = {
  if (xs == Nil) {            //case Nil
    None
  } else {                    // case y::ys
    val y = xs.head
    val ys = xs.tail
    val zoption = maximum (ys)
    if (zoption == None) {    // case None
      Some (y)
    } else {                  // case Some(z)
      val z = zoption.get
      Some (y max z)
    }
  }
}

def find [X] (xs:List[X], p:X=>Boolean) : Option[X] = {
  xs match {
    case Nil            => None
    case y::ys if p (y) => Some (y)
    case _::ys          => find (ys, p)
  }
}

def p = (x:Int) => (x==5)

find(List(11,5,21), p)
=> find(List(5,21), p)
=> Some(5)

find(List(11,21), p)
=> find(List(21), p)
=> None

def oneFind (xs:List[String], s:String) : Option[String] = {
  xs.find ((x:String) => (x.length > s.length) && x.contains (s))
}

def twoFind (xs:List[String], s:String) : Option[String] = {
  oneFind (xs, s) match {
    case None     => None
    case Some (t) => oneFind (xs, t)
  }
}

def oneFind (xs:List[String], s:String) : Option[String] = {
  xs.find ((x:String) => (x.length > s.length) && x.contains (s))
}

def twoFind (xs:List[String], s:String) : Option[String] = {
  oneFind (xs, s).flatMap ((t:String) => oneFind (xs, t))
}

(let loop ([n 1])
  (if (> n 4)
      ()
      (begin
        (display (string-append (number->string n) " potato\n"))
        (loop (+ n 1)))))

(define (foo n)
  (if (> n 4)
      ()
      (begin
        (display (string-append (number->string n) " potato\n"))
        (foo (+ n 1)))))

import scala.annotation.tailrec

@tailrec
def foo (n:Int) : Unit =
  if n <= 4 then 
    println ("%d potato".format (n))
    foo (n + 1)

(define (count-aux xs low high result) 
  (if (equal? xs ())
      result
      (if (and (<= low (car xs)) (<= (car xs) high))
          (count-aux (cdr xs) low high (+ 1 result))
          (count-aux (cdr xs) low high result))))

(define (count xs low high) 
  (count-aux xs low high 0))


; Alternative version

(define (count-alternate xs low high) 
  (let loop ([xs xs] [result 0])
    (if (equal? xs ())
        result
        (if (and (<= low (car xs)) (<= (car xs) high))
          (loop (cdr xs) (+ 1 result))
          (loop (cdr xs) result)))))

def count (xs:List[Int], low:Int, high:Int) : Int =
  def aux (ys:List[Int], result:Int) : Int =
    ys match
      case Nil                            => result
      case z::zs if low <= z && z <= high => aux (zs, result + 1)
      case _::zs                          => aux (zs, result)
  aux (xs, 0)

def repeat [X] (x:X, n:Int) : List[X] = {
  if n == 0 then 
    Nil
  else 
    x :: repeat (x, n - 1)
}

val xs:List[(Char,Int)] = List (('a', 2), ('b', 4), ('c', 8))

val ys = xs.map ((p:(Char,Int)) => repeat (p._1, p._2))

val zs = xs.flatMap ((p:(Char,Int)) => repeat (p._1, p._2))

val zs2 = xs.map ((p:(Char,Int)) => repeat (p._1, p._2)).flatten

(zs == zs2)

object Counter:
  private var numCounters = 0

  def getNumCounters : Int = numCounters
  def incNumCounters : Unit = numCounters = numCounters + 1

class Counter (initial:Int):
  private val id:Int = Counter.getNumCounters
  private var count:Int = initial
  Counter.incNumCounters

  def getId () : Int = id
  def getNextCount () : Int = { val tmp = count; count = count + 1; tmp }

enum MyList[+X]:
  case MyNil
  case MyCons(head:X, tail:MyList[X])
import MyList.*

def length [X] (xs:MyList[X]) : Int =
  xs match
    case MyNil => 0
    case MyCons (_, ys) => 1 + length (ys)

def toList [X] (xs:MyList[X]) : List[X] =
  xs match
    case MyNil => Nil
    case MyCons (y, ys) => y::toList(ys)

def fromList [X] (xs:List[X]) : MyList[X] =
  xs match
    case Nil => MyNil
    case y::ys => MyCons (y, fromList (ys)) 

def append [X] (xs:MyList[X], ys:MyList[X]) : MyList[X] =
  xs match
    case MyNil => ys
    case MyCons (z, zs) => MyCons (z, append (zs, ys)) 

def map [X,Y] (xs:MyList[X], f:X=>Y) : MyList[Y] =
  xs match
    case MyNil => MyNil
    case MyCons (y, ys) => MyCons (f (y), map (ys, f)) 

val xs = MyCons(11, MyCons(21, MyCons(31, MyNil)))
val len = length (xs)

enum Tree[+X]:
  case Leaf
  case Node(l:Tree[X], c:X, r:Tree[X])
import Tree.*

val tree1:Tree[Int] = Leaf

val tree2:Tree[Int] = Node (Leaf, 5, Leaf)

val tree3:Tree[Int] = Node (Node (Leaf, 2, Leaf), 3, Node (Leaf, 4, Leaf))

// Find the size of a binary tree.  Leaves have size zero here.
def size [X] (t:Tree[X]) : Int =
  t match
    case Leaf => 0
    case Node (t1, _, t2) => size (t1) + 1 + size (t2)

// Insert a number into a sorted binary tree.
def insert [X] (x:X, t:Tree[X], lt:(X,X)=>Boolean) : Tree[X] =
  t match
    case Leaf => Node (Leaf, x, Leaf)
    case Node (t1, c, t2) if (lt (x, c)) => Node (insert (x, t1, lt), c, t2)
    case Node (t1, c, t2) if (lt (c, x)) => Node (t1, c, insert (x, t2, lt))
    case Node (t1, c, t2)                => Node (t1, c, t2)

// Put the elements of the tree into a list using an in-order traversal.
def inorder [X] (t:Tree[X]) : List[X] =
  t match
    case Leaf => Nil
    case Node (t1, c, t2) => inorder (t1) ::: List (c) ::: inorder (t2)