Homework #1

CS 152 | Fall 2008 | Due Date: 2008-09-16 23:59

You may not use any var in this homework.

Problem 1: Simple Recursion

Using nothing but head, tail, ::, isEmpty, if, and recursion, write two functions

append(a : List[Int], b : List[Int]) : List[Int]
reverse(a : List[Int]) : List[Int]

To be totally clear: You cannot use any other Scala library functions.

10 points, and 5 points extra credit if your reverse runs in O(n) time, where n is the length of the list. Hint: Use a helper function so that the computation looks like this:

() (1 2 3)
(1) (2 3)
(2 1) (3)
(3 2 1) ()

Problem 2: A Functional Data Structure

Implement three functions that implement a functional data structure: a map from strings to integers (just like Map<String, Integer> in Java or Map[String, Int] in Scala). Your internal representation must be a list of pairs List[(String, Int)]. Provide three functions

put adds a new pair into the map, or replaces an existing key with a new value. The returned value is the new map. (The old map is not changed.)
get gets the value for a given key, or 0 if the key is not present. (There is a much better way of doing this in Scala, by using the Option type, but you should not do that for this assignment.)
keys gets a list of all keys (doesn't matter in which order)

Sample usage:

val map1 = List[(String, Int)]()
val map2 = put(map1, "Harry", 17) // yields List((Harry,17))
val map3 = put(map2, "Sally", 18)
val map4 = put(map3, "Sally", 29)
val x = get(map4, "Sally") // yields 29
val k = keys(map4) // yields List("Harry", "Sally") 
  // or List ("Sally", "Harry")

You can use any of the Scala library functions, or just simple recursion. Efficiency does not matter.

15 points

Problem 3: Working with Predicate Functions

Read through the description of the partition list function in scaladoc. Write a function

partition(lst : List[Int], pred : (Int) => Boolean) : List[List[Int]]

that has the same effect but that returns a list of the two result lists. Your function body must end in the following call:

List(lst.filter(.....), lst.filter(.....))

Your task is simply to provide the two function arguments for filter.

Here is an example call:

partition(List(1, 2, 3, 4), (x : Int) => x % 2 == 0) 
  is List(List(2, 4), List(1, 3))

5 points

Problem 4: Folding

Horner's method for evaluating a polynomial uses folding, like in this example:

2 x³ + 3 x² - x + 5= (((2 · x + 3) · x - 1) · x + 5

Write a function

evalPoly(coeffs : List[Double], x : Double) : Double

that computes the result using the /: operator. For example,

evalPoly(List(2, 3, -1, 5), 2) is 31

5 points

Problem 5: Right Folding

The following function removes all adjacent duplicates from a list, but it is quite inefficient.

def removeAdjacentDuplicates(lst : List[Int]) = 
  (List(lst.head) /: lst) ((partialResult, nextElement) => 
    if (partialResult.last == nextElement) 
      partialResult else 
      partialResult + nextElement)

The last and + are O(n) operations, where n is the length of the list argument, making this function O(n²) since they execute in a loop. Your task is to reimplement the function by using :\, building up the result from the end in O(n) time.

10 points

Problem 6: Event Handling

The following program is a partial translation to Scala of this program from Big Java. Your task is to complete the two functions.

import java.awt._
import javax.swing._
import javax.swing.event._

// This makes an implicit conversion from a function to a change listener
// We wouldn't need this if the Java API was functional
implicit def makeChangeListener(action : (ChangeEvent)=>Unit) = new ChangeListener {
    override def stateChanged(event: ChangeEvent) { action(event) } 
  }

val frame = new JFrame
  
val colorPanel = new JPanel
frame.add(colorPanel)

val controlPanel = new JPanel
controlPanel.setLayout(new GridLayout(3, 2))
frame.add(controlPanel, BorderLayout.SOUTH)

val redSlider = new JSlider(0, 255, 255)
val greenSlider = new JSlider(0, 255, 175)
val blueSlider = new JSlider(0, 255, 175)

def setSampleColor() {
  ...
}

def addSlider(label : String, slider : JSlider) {
  ...
}

addSlider("Red", redSlider)
addSlider("Green", greenSlider)
addSlider("Blue", blueSlider)

frame.setSize(400, 400)
frame.setVisible(true)
setSampleColor()

10 points

Submission Instructions

Make a zip file with name hw1_lastname_firstname.zip, substituting your own names (duh). The extension must be in lowercase. The file must have no subdirectories and contain of six files problem1.scala ... problem6.scala. Each of these files should contain only the definitions of the required functions, nothing else. My grading script

extracts your name from the file name by removing the first and last four letters
unzips your file into that directory
Runs cat problem1.scala test1.scala | scala etc. for each of the problems, (where test1.scala contains my test cases for problem 1)

5 points if you follow all of these instructions so that my grading script runs without requiring manual adjustments. Upload your solution to eCampus. You can submit as often as you like; only your last submission counts. Please note that eCampus will reject your submission after the due date.

For an additional 5 points, put your photo and bio onto eCampus. If it is already there, you'll get those 5 points. (If for whatever reason you do not want to provide a photo of yourself, provide a photo of your laptop instead.)

Final Remarks

My solution to this homework is < 40 lines. But I doubt very much that you can whip up these lines a few hours before the deadline. I suggest you start today and ask lots of questions on the eCampus discussion group.