Scala Assignments - Note not all are fully functional

Arrays and Matrices

//==================================================
//
// Homework 2, Part B
//
// Name: Kristofer Hult
//
//==================================================


//================================================
// Vec
//================================================

class Vec private (private val elems:Array[Double]) {
  val length = elems.length
  
  def this(x:Double) = this(Array(x))

  def apply(i:Int) = elems(i)
  
  def ++(other:Vec) = {
    val r_length = length + other.length
    val r_elems = new Array[Double](r_length)
    for (i <- 0 to length - 1) r_elems(i) = elems(i)
    for (i <- 0 to other.length - 1) r_elems(length + i) = other.elems(i)
    new Vec(r_elems)
  }

  def +(other:Vec) = {
    val r_elems = new Array[Double](length)
    for (i <- 0 to length - 1) r_elems(i) = elems(i) + other.elems(i)
    new Vec(r_elems)
  }
  
  def *(other:Vec) = {
    var p = 0.0
    for (i <- 0 to length - 1) 
      p = p + (elems(i) * other.elems(i))
    p
  }
  
  override def toString = {
    var s = "<" + this.apply(0)
    for (j <- 1 to length - 1)
      s = s + ", " + this.apply(j)
    s + ">"
  }

  // overrides the default definition of == (an alias of equals)
  override def equals(other:Any):Boolean = other match {
    // if other is an instance of Vec then ...
    case o:Vec =>
      for (j <- 0 to length - 1)
        if (this.apply(j) != o.apply(j)) return false
      true
    // otherwise return false
    case _ => false
  }
}


//================================================
// Matrix
//================================================

// Suggestion: for testing purposes it is convenient
//             to implement toString first


// (The main constructor of) Matrix takes as input
// an array of n > 0 vectors all of the same length 
class Matrix private (a:Array[Vec]) {

  // Public constructor
  def this(v:Vec) = this(Array(v))
  def this(x:Double) = this(new Vec(x))
 
  // the array is stored as is in the private field rows
  // the element at position (i,j) in the matrix is stored
  // as the j-th element of the i-th vector in rows
	 private val rows = a

	// integer field h stores the height of the matrix
 val h = {rows.length}
	
 // integer field w stores the width of the matrix
 val w = {rows(0).length }
	
 /* given i in [0 .. h-1] and j in [1 .. w-1],
    apply(i,j) returns the matrix element at position (i,j)
 */
 def apply(i:Int, j:Int) = {
   rows(i).apply(j)
 }
	/* given a matrix other with other.w == w,
	   /(other) returns a new matrix m such that
	   - m.h == h + other.h
	   - m.w == w
	   - for all i in [0 .. h-1] and j in [0 .. w-1],  m(i,j) == this(i,j)
	   - for all i in [h .. r.h-1] and j in [0 .. w-1],  m(i,j) == other(i,j)
	*/
	def /(other:Matrix) = {
	    val mLength = h + other.h
      val vectors = new Array[Vec](mLength)
 
      for (i <- 0 to h - 1) {
             vectors(i) = new Vec(apply(i, 0))
             for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
                }
      for (i <- 0 to other.h - 1) {
             vectors(i + h) = new Vec(other.apply(i, 0))
             for (j <- 1 to w - 1) vectors(i + h) ++= new Vec(other.apply(i, j))
                }
      new Matrix(vectors)
}
	
	/* given a matrix other with other.h == h,
	   ++(other) returns a new matrix m such that
	   - m.h == h 
	   - m.w == w + other.w
	   - for all i in [0 .. h-1] and j in [0 .. w-1],  m(i,j) == this(i,j)
	   - for all i in [0 .. h-1] and j in [w .. r.w-1],  m(i,j) == other(i,j)
	*/
	def ++(other:Matrix) = {
	  val mLength = w + other.w
    val vectors = new Array[Vec](h)
 
    for (i <- 0 to h - 1) {
           vectors(i) = new Vec(apply(i, 0))
           for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j))
           for (j <- 0 to other.w - 1) vectors(i) ++= new Vec(other.apply(i, j))
           }
    new Matrix(vectors)
}
	/* given a matrix other with other.h == h and other.w == w,
	   +(other) returns a new matrix m such that
	   - m.h == h 
	   - m.w == w 
	   - for all i in [0 .. h-1] and j in [0 .. w-1],
	     m(i,j) == this(i,j) + other(i,j)
	*/
	def +(other:Matrix) ={
      val vectors = new Array[Vec](h)
      for (i <- 0 to h - 1) {
          vectors(i) = new Vec(apply(i, 0))
          for (j <- 1 to w - 1) vectors(i) ++= new Vec(apply(i, j) + other.apply(i, j))
                }
      new Matrix(r_vecs)
        }

 /* given a j in [0 .. w-1],
    col(j) returns a vector v whose elements come 
    from the j-th column of the matrix, i.e.,
    - v.length == h
    - for all i in [0 .. h-1] ,  v(i) == this(i,j)  
 */
  private def col (j:Int) = {
   var c = new Vec(rows(0)(j))
   for (i <- 1 to h - 1)
     c = c ++ new Vec(rows(i)(j))
   c
 }

	/* transpose returns a new matrix m such that
	   - m.h == w 
	   - m.w == h
	   - for all i in [0 .. m.h-1] and j in [0 .. m.w-1],  m(i,j) == this(j,i)

	   Suggestion: use method col
	*/
 def transpose =  {
     val vectors = new Array[Vec](h)
     for (i <- 0 to h - 1) r_vecs(i) = col(i)
     new Matrix(vectors)
        }
  
  
  /* given an i in [0 .. h-1], rowToString(i) 
    returns a string of the form  | d1 d2 ... dw |
    where d1, ..., dw are the (the string representation of)
    the elements in row i 
 */
 private def rowToString(i:Int) = {
   var s = "| "
   for (j <- 0 to w - 1) 
     s = s + this.apply(i,j) + " "
   s ++ "|"
 }

/* toString returns a string of the form

   | d_00 d_01 ... d_0q |
   | d_10 d_11 ... d_1q |
   |  .    .        .   |
   |  .    .        .   |
   |  .    .        .   |
   | d_p0 d_p1 ... d_pq |
   
   where d_ij is the (the string representation of) this(i,j)
 */
 override def toString = {
     var out:String = "";
     for (i <- 0 to h - 1) out ++= rowToString(i) + "\n"
     out
        }

 // overrides the default definition of == (an alias of equals)
 override def equals(other:Any):Boolean = other match {
   // if o is an instance of Matrix then ...
   case o:Matrix =>
     for (i <- 0 to h - 1; j <- 0 to w - 1)
       if (this(i,j) != o(i,j)) return false
     true
		// otherwise return false
		case _ => false
  }
}


// A few test cases you could try
val m1 = new Matrix(1) ++ new Matrix(2) ++ new Matrix(3) 
val m2 = new Matrix(4) ++ new Matrix(5) ++ new Matrix(6)
val m3 = m1 / m2 / m1
val m4 = m1 ++ m2


val m = new Matrix

Classes

//==================================================
//
// Homework 3
//
// Name: Kristofer Hult
//
//==================================================

/* Generic abstract class for finite sets */
abstract class FinSet[T] protected () {
	 /* returns a list consisting of the set's elements */
  def toList:List[T]

  /* given a value x, it retuns a new set consisting of x
     and all the elemens of this (set)
  */
  def +(x:T):FinSet[T]

  /* given a set other, it returns the union of this and other,
     i.e., a new set consisting of all the elements of this and
     all the elements of other
  */
  def U(other:FinSet[T]):FinSet[T]  

  /* given a set other, it returns the intersection of this and other,
     i.e., a new set consisting of all the elements that occur both
     in this and in other
  */
  def ^(other:FinSet[T]):FinSet[T]

  /* given a set other, it returns the difference of this and other,
     i.e., a new set consisting of all the elements of this that
     do not occur in other
  */
  def \(other:FinSet[T]):FinSet[T]
  
  /* given a value x, it retuns true if and only if x is an element of this 
  */
  def contains(x: T):Boolean
   
  /* given a set other, it returns true if and only if this is included
     in other, i.e., iff every element of this is an element of other
  */
  def <=(other:FinSet[T]):Boolean = {
  	case o:FinSet[T] =>  (this <= o)
    case _ => false
  }
  
  override def toString = "{" ++ (toList mkString ", ") ++ "}"
  
  // overrides the default definition of == (an alias of equals)
  override def equals(other:Any):Boolean = other match {
    // if other is an instance of FinSet[T] then ...
    case o:FinSet[T] => 
      // it is equal to this iff it includes and is included in this
      (this <= o) && (o <= this)
    case _ => false
  }
  // Note: compiling the method equals above may produce this warning:
  // "there were 1 unchecked warnings; re-run with -unchecked for details"
  // You can ignore it
}


/* Generic concrete class implementing finite sets internally 
   as lists with no repetitions
*/
// Precoditions: the input list l has no repeated elements
class ListSet[T] private (l: List[T]) extends FinSet[T] {
  def this() = this(Nil)
  
  // invariant: elems is a list with no repetitions
  //            storing all of the set's elements 
  private val elems = l

  /* this method can be useful in implementing some of the methods
     from FinSet. Given a value x and a list l with no repetitions,
     it returns a list with no repetitions consisting
     of x and all the elements of l
  */ 
  private def add(x:T, l:List[T]):List[T] = l match {
    case Nil => x :: Nil
    case y :: t => if (x == y) l else y :: add(x, t)
  }
    
  val toList = elems   /* returns a list consisting of the set's elements */
    

  def +(x: T) = {												
  	new ListSet[T](this.add(x, elems))/* given a value x, it retuns a new list consisting of x
     																	and all the elemens of this (set)
  																		*/
  }
    

  def U(other:FinSet[T]) = {
  	/* given a list other, it returns the union of this and other,
     i.e., a new list consisting of all the elements of this and
     all the elements of other
  	*/
  	var UList=List[T]()
  	for(i<-other.toList){
  		UList=this.add(i,UList)
  	}
  	new ListSet[T](UList)
  }
  
  def ^(other:FinSet[T]) = {
   /* given a list other, it returns the intersection of this and other,
     i.e., a new list consisting of all the elements that occur both
     in this and in other
   */
   var IList=List[T]()
   for(i<-other.toList){
  		if(elems.contains(i){
  			IList=i::IList
  		}
  	}
   new ListSet[T](IList)
  }
  
  def \(other:FinSet[T]) = {
  	/* given a list other, it returns the difference of this and other,
     i.e., a new list consisting of all the elements of this that
     do not occur in other
  	*/
  	var DiffList=List[T]()
  	for(i<-elems){
  		if(!other.contains(i)){
  			DiffList=i::DiffList
  		}
  	}
  	
  }
    

  def contains(x:T) = {
  	/* given a value x, it retuns true if and only if x is an element of this 
   */
    for(i<-other.toList){
    	if(x==toList[i])
    }
}



/* Generic concrete class implementing finite sets internally
   as immutable Maps from T to Unit
*/
class MapSet[T] private (m: Map[T, Unit]) extends FinSet[T] {
  def this() = this(Map())

  // invariant: the pair (x, ()) is in the map elems if and
  //            only if x is an element of the set 
  private val elems = m

  /* This method can be useful in implementing toList. Given 
     - a list List( (x1,()), ..., (xm,()) ) and 
     - a list List( y1, ..., yn ), it returns the list
     List( yn, ..., y1, xm, ..., m1 )
  */ 
  private def project(l1:List[(T, Unit)], l2:List[T]):List[T] =
    l1 match {
      case Nil => l2
      case (x, _) :: t => project(t, x :: l2)
    }
  
  val toList = elems.keys 
   
   
  def +(x:T) =  new.MapSet[T](elems +(x->()))
    
  def U(other:FinSet[T]) =  {
  	var UMap=elems
  	for(i<-other.toList){
  		UMap=UMap+(i ->())
  	}  	
  	new MapSet[T](UMap)
  }
    
  
  def ^(other:FinSet[T]) =  {
  	var IMap=Map[T,Unit]()
  	for(i <-other.toList){
  		if(elems.contains(i){
  			IMap=IMap+(i -> ())
  		}
  	}
  	new MapSet[T](IMap)
  }
      
  def \(other:FinSet[T]) =  {
  	var DiffMap=Map[T,Unit]()
  	for(i<-elems){
  		if(!other.contains(i)){
  			DiffMap=DiffMap+(i -> ())
  		}
  	}
  	new MapSet[T](DiffMap)
  }

  def contains(x:T) =  elems.contains(x)
}



/* some test cases for ListSet

val empty = new ListSet[Int]

val s1 = empty + 1

val s2 = empty + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4
 
s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/


/* same test cases but for MapSet

val empty = new MapSet[Int]

val s1 = empty + 1

val s2 = empty + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4
 
s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/


/* Same test cases but mixing ListSet and MapSet instances
   In a correct implementation ListSet and MapSet should be
   interchangeable

val empty = new ListSet[Int]

val s1 = empty + 1

val s2 = (new MapSet[Int]) + 2

val s12 = s1 U s2

val s21 = s2 U s1

s1 == s12 // should return false

s21 == s12 // should return true

s12 U s1 // should return a set equal to s12

val s123 = s12 + 3

val s23 = empty + 2 + 3

val s234 = s23 + 4
 
s123 ^ s234  // should evaluate to a set equal to s23

s123 \ s234  // should evaluate to a set equal to s1

s12 \ s21  // should evaluate to an empty set

s23 contains 2  // should evaluate to true

s23 contains 4  // should evaluate to false

s23 <= s123  // should evaluate to true

s23 <= s234  // should evaluate to true

s23 <= s23  // should evaluate to true

s1 <= s23 // should evaluate to false

*/

Using Dictionaries

//==================================================
//
// Homework 2, Part A
//
// Name: Kristofer Hult
//
//==================================================


abstract class Dictionary {
  
  /* put(k,v) adds value v to the dictionary under key k.  
     put may be called with the same key multiple times,
     all key->values pairs get stored in the dictionary
  */
  def put(key:String, value: Any):Unit

  /* get(k) returns Some(v) where v is one of the values 
     associated with key k in the dictionary, if any.
     It returns None if k is associated to no value.
  */   
  def get(key:String):Option[Any]

   /* remove(k) removes one value v associated with key k
      from the dictionary, if any, and returns it as Some(v).  
      It returns None if k is associated to no value.
  */   
  def remove(key:String):Option[Any]

 /* toList() returns a list containing all the key/value pairs 
    in the dictionary.
    If multiple values have the same key k, each is listed
    in a separate pair with k.
   */
   def toList():List[(String,Any)]

 /* toString() returns a string containing all the key/value pairs 
     in the dictionary. The string has the form 
     
        Dictionary(key_1 -> value_1, ..., key_n -> value_n)
     
     where each key_i is a key and each value_i is (the string
     representation of) the corresponding value.
     If multiple values have the same key k, each is present
     in a separate pair with k.
   */
   override def toString():String

  /* getAll(k) returns the list of all the values associated
     with key k in the dictionary.
  */   
  def getAll(key:String):List[Any] ={
    var l = List[Any]()
    for ((k,v) <- toList)
      if (k == key) l = Any::l
    l
  }
  

  /* removeAll(k) removes from the dictionary all the values 
     associated with key k in the dictionary, if any.
  */   
  def removeAll(key:String) = {
    while (get(key) != None)
      remove(key)
}



class ListDictionary extends Dictionary {
  /* the dictionary is implemented using a list of key/value pairs */
  private var d = List[(String,Any)]()
  
  /* put(k,v) adds value v to the dictionary under key k.  
     put may be called with the same key multiple times,
     all key->values pairs get stored in the dictionary
  */
  def put(key:String, value: Any):Unit={
  	d=(key, value)::d
  }

  /* get(k) returns Some(v) where v is one of the values 
     associated with key k in the dictionary, if any.
     It returns None if k is associated to no value.
  */   
  def get(key:String):Option[Any]= {
    for ((a,x) <- d)
      if (a == key) return Some(x)
    None
  }

  def remove(key:String):Option[Any]

 /* toList() returns a list containing all the key/value pairs 
    in the dictionary.
    If multiple values have the same key k, each is listed
    in a separate pair with k.
   */
def toList():List[(String,Any)]={
    var l = List[(key,value)]()
    for (a <- d; element <- a)
	    l = element::l
    l
  }

 /* toString() returns a string containing all the key/value pairs 
     in the dictionary. The string has the form 
     
        Dictionary(key_1 -> value_1, ..., key_n -> value_n)
     
     where each key_i is a key and each value_i is (the string
     representation of) the corresponding value.
     If multiple values have the same key k, each is present
     in a separate pair with k.
   */
   override def toString():String={
   	var d=toList();
    def toStringSecondary(l:List[(key,value)]):String =
      l match {
        case Nil => ""
        case (k,v)::Nil => k + " -> " + v
        case (k,v)::t => k + " -> " + v + ", " + toStringSecondary(t)
      }

    "Dictionary(" + toStringSecondary(d) + ")"
  }
   }

    
}

Using Variables

/*==================================================
    
    Homework 1
    
    Name: Kristofer Hult

  ==================================================
*/

//---------
// Part 1
//In the following problems do not dene methods recursively. Instead, use mutable variables and
//while or for loops as needed in method denitions. You may use auxiliary methods if needed.
//---------

/* Problem 1.1 */
def mul (m: Int, n: Int):Int =
{
for(i <- 1 to m){  //for loop that starts at 1 and goes until the value given for m
  if(m==0 || n==0){ //if m or n is zero the result will be zero
    0 
  }
  else{
    var x:Int+=x+n// adds value of n until it reaches the value of m, gives result of n * m 
}
}
}

/* Problem 1.2 */
def concatAll (l: List[String]) :String=
{
for(i <- 0 to l.length){		//for loop that starts at zero and goes to the length of list l
  var combination: string +=l[i] //combines the list together to form a word
}
}
/* Problem 1.3 */
def isIn (x: Int, l: List[Int]) :Boolean
{
for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l

  if (x=l[i])			{		//checks to see if x is equal to the ith place in list l. returns true if it is in and goes to i+1 if not.
   true
  }
}
}
/* Problem 1.4 */
def squareAll (l: List[Int]) :List[Int]=
{
for(i <- 0 to l.length){	// starting with 0 this loop takes each element 
  h::(l[i]*l[i])				//in the list and multiplies it by itself
}
}
//---------
// Part 2
//In the following problems do not use any mutable variables (i.e., variables declared with var) or
//any mutable predened types such as arrays, mutable sets, and so on. You may dene methods
//recursively this time. Do not use the if operator in Problems 1-4 below.
//---------

/* Problem 2.1 */
def mul (m: Int, n: Int) :Int=
{
	n match{
		case 0 => 0// if n is zero the answer is zero
		case _=>	m match{
								case 0 => 0		//if m is zero answer is zero
								case _ => n+mul(m-1,n) // adds n to n until m is zero
		}
	}
}
	
/* Problem 2.2 */
def concatAll (l: List[String]) :String=
{
for(i <- 0 to l.length){		//for loop that starts at zero and goes to the length of list l
  var combination: string +=l[i] //combines the list together to form a word
}
}
/* Problem 2.3 */
def isIn (x: Int, l: List[Int]) :Boolean
{
for(i <- 0 to l.length){//for loop that starts at zero and goes to the length of list l
		x match{
			case l[i] => true //returns true if x = l[i]
			case _ => Nil
		}
}
}
  

/* Problem 2.4 */
def squareAll (l: List[Int]) :List[Int]=
{
for(i <- 0 to l.length){	// starting with 0 this loop takes each element 
  h::(l[i]*l[i])				//in the list and multiplies it by itself
}
}
/* Problem 2.5 */
def remove (x: Int, l: List[Int]) :List[Int]=
{
	l.remove(x) // takes list l and removes x from list
	
}
/* Problem 2.6 */
//For each method write in a Scala comment a concise description in English of its functionality,
//along the lines of the descriptions provided for the methods in the previous problems (given
//this and that, it returns so and so). Just describe the input-output behavior of the method,
//not the internal algorithm.
def m(l1:List[Int], l2:List[Int]):List[Int] = // takes two lists of integers
 (l1, l2) match {
  case (Nil, _) => l2		// if list 11 is empty return list l2
  case (_, Nil) => l1		// if list 12 is empty return list l1
  case (h1 :: t1, h2 :: t2) => {
   if (h1 < h2)
    h1 :: m(t1, l2)		// if head of list l1, h1, is greater than the head of list l2, h2, return h1 and recursive call m(t1, l2) and repeat the process
   else
    h2 :: m(l1, t2)		// if head of list l2, h2, is greater than the head of list l2, h1, return h1 and recursive call m(l1, t2) and repeat the process
 }										// END RESULT is one list of the lowest values to highest values from lists l1 and l2
}
def s(l:List[Int]) = {
 def s_aux(l0:List[Int], l1:List[Int], l2:List[Int]):(List[Int], List[Int]) =
  l0 match {
   case Nil => (l1, l2) //If list l0 is empty return (l1, l2)
   case x :: Nil => (x :: l1, l2) // if there is nothing after x it adds l1 and l2 to a list with x at the front
   case x1 :: x2 :: t => s_aux(t, x1 :: l1, x2 :: l2) // if no match it returns to the start.
  }
 s_aux(l, Nil, Nil)
}

/* Problem 2.7 */
def pair (list1: List[Int], list2: List[Int]) :List[(Int,Int)]=

/* Problem 2.8 */
def mergeSort (l: List[Int]) :List[Int]=