CS 331 Spring 2013
Assignment 4

Assignment 4 is due at 5 p.m. Sunday, March 3. It is worth 20 points.

Procedures

E-mail answers to the exercises below to ggchappell@alaska.edu, using the subject “PA4”.

• Your answers should consist of two files: the answer to Exercise A, and PA4.hs from Exercise B. These two files (or a single archive file containing them) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (20 pts total)

Exercise A — Running a Haskell Program

Purpose

In this exercise you will make sure you can execute Haskell code.

Instructions

Run the program check_haskell.hs (on the class web page). Tell me what it does.

If you use the AOT compiler (GHC), then compile the program and run the resulting executable. If you use an interactive environment (GHCi or Hugs), then load the source file and run function main.

Exercise B — Writing Haskell Code

Purpose

In this exercise, you will write some simple Haskell functions, including one infix operator.

Instructions

Write a Haskell module PA4, contained in the file PA4.hs (note the capitalization in the filename!). Module PA4 should include the following five public functions/variables/operators: filterAB, collatzCounts, findList, ##, sumEvenOdd.

• Function filterAB. This takes a boolean function and two lists. It returns a list of all items in the second list for which the corresponding item in the first list makes the boolean function true.

  Examples:

  • filterAB (>0) [-1,1,-2,2] [1,2,3,4,5,6] should return [2,4].
  • filterAB (==1) [2,2,1,1,1,1,1] "abcde" should return "cde".
• Variable collatzCounts. This is a list of integers. Item \(k\) (counting from zero) of collatzCounts tell how many iterations of the Collatz function are required to take the number \(k+1\) to \(1\).

  The Collatz function is the following function \(f\).

  \[ f(n) = \begin{cases} 3n+1, & \text{if } n \text{ is odd;}\\ n/2, & \text{if } n \text{ is even.} \end{cases} \]

  So, for example, item 0 of collatzCounts is 0, since no applications of the Collatz function are required to make \(0+1=1\) turn into \(1\). Item 2 of collatzCounts is 7. Since, starting with \(2+1=3\), it requires \(7\) steps to get to \(1\).

  1. \(3\) is odd, so \(f(3) = 3\cdot 3 + 1 = 10\).
  2. \(10\) is even, so \(f(10) = 10/2 = 5\).
  3. \(5\) is odd, so \(f(5) = 3\cdot 5 + 1 = 16\).
  4. \(16\) is even, so \(f(16) = 16/2 = 8\).
  5. \(8\) is even, so \(f(8) = 8/2 = 4\).
  6. \(4\) is even, so \(f(4) = 4/2 = 2\).
  7. \(2\) is even, so \(f(2) = 2/2 = 1\).

  Example:

  • take 10 collatzCounts should return [0,1,7,2,5,8,16,3,19,6].

  Something you may find useful: The Haskell function div does integer division. For example, div 17 2 returns 8.

• Function findList. This takes two lists. It returns a tuple containing a Bool and an integer. It the first list is found as a continguous sublist of the second list, then the Bool is True and the integer is the index (starting from zero) at which the copy of the first list begins. If the first list is not found as a contiguous sublist of the second, then the Bool is False and the integer can be any value.

  Examples:

  • findList "cde" "abcdefg" should return (True,2).
  • findList "cdX" "abcdefg" should return (False,???), where “???” is replaced by some integer.
  • findList [1] [2,1,2,1,2] should return (True,1).
  • findList [] [1,2,3,4,5] should return (True,0).
• Infix operator ##. The two operands are lists. The return value is an integer giving the number of indices at which the two lists contain equal values.

  Examples

  • [1,2,3,4,5] ## [1,1,3,3,9,9,9,9] should return 2.
  • [] ## [1,1,3,3,9,9,9,9] should return 0.
  • "abcde" ## "aXcXeX" should return 3.
  • "abcde" ## "XaXcXeX" should return 0.
• Function sumEvenOdd. This takes a list of numbers. It returns a tuple of two numbers: the sum of the even-index items in the given list, and the sum of the odd-index items in the given list.

  You must implement sumEvenOdd using a “fold” function: foldl, foldr, foldl1, or foldr1, as follows.

  sumEvenOdd ... = fold... ...
  

  The “...” above are replaced by other code.

  Examples:

  • sumEvenOdd [1,2,3,4] should return (4,6).
  • sumEvenOdd [20] should return (20,0).
  • sumEvenOdd [] should return (0,0).
  • sumEvenOdd [1,1,1,1,1,1,1] should return (4,3).

Code Structure

• To write your module, start your file (after the initial comments) with

  module PA4 where

Test Program

A test program is available: pa4_test.hs. This will test whether your package works properly. (It will not test whether sumEvenOdd is implemented as required.)

If you are using GHCi (or Hugs), then put your file and the test program in the same directory, and do

> :l pa4_test
> main

(Note that “> ” represents the GHCi prompt, and is not to be typed.)

Do not turn in pa4_test.hs.