CS 331 Spring 2013 > Assignment 4 |
Assignment 4 is due at 5 p.m. Sunday, March 3. It is worth 20 points.
E-mail
answers to the exercises below to
ggchappell@alaska.edu
,
using the subject
“PA4
”.
PA4.hs
from Exercise B.
These two files (or a single archive file containing them)
should be attached to your e-mail message.In this exercise you will make sure you can execute Haskell code.
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
.
In this exercise, you will write some simple Haskell functions, including one infix operator.
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
.
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"
.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
is0
, since no applications of the Collatz function are required to make \(0+1=1\) turn into \(1\). Item 2 ofcollatzCounts
is7
. Since, starting with \(2+1=3\), it requires \(7\) steps to get to \(1\).
- \(3\) is odd, so \(f(3) = 3\cdot 3 + 1 = 10\).
- \(10\) is even, so \(f(10) = 10/2 = 5\).
- \(5\) is odd, so \(f(5) = 3\cdot 5 + 1 = 16\).
- \(16\) is even, so \(f(16) = 16/2 = 8\).
- \(8\) is even, so \(f(8) = 8/2 = 4\).
- \(4\) is even, so \(f(4) = 4/2 = 2\).
- \(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
.
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)
.
##
.
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
.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)
.module PA4 where
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
.
ggchappell@alaska.edu