# HW 1 - Haskell List Processing and recursion

This is the first homework assignment for CIS 552. It provides practice with the basic built-in data structures of Haskell, including lists, tuples and maybes, as well as recursion and pattern matching. It also covers the basics of code style and test-driven development.

This file is a "literate" Haskell program, meaning that explanation is interspersed with actual Haskell code. To complete your assignment, edit this file, which contains *just* the code, and submit it through the course web page. Make sure the beginning of the file contains your name and your partner's name in the comments.

Make sure the beginning of the file contains your name and your partner's name in the comments.

```
-- Advanced Programming, HW 1
-- by <YOUR NAME HERE>, <YOUR PENNKEY>
-- and <PARTNER NAME>, <PARTNER PENNKEY>
```

Before we go any further, you should make sure that you can compile and run this code. Under emacs: C-c C-l will load the it interactively into ghci. You can then type `main`

to run the main routine. Alternatively, to compile the code from the command line type

` ghc --make Main`

which will produce an executable (named `Main`

, `a.out`

or `Main.exe`

depending on your system).

The first line of actual code for this homework assignment is a few pragmas to GHC (these are specific instructions for the compiler.)

`{-# OPTIONS -Wall -fwarn-tabs -fno-warn-type-defaults #-}`

The first option controls what warnings we would like GHC to generate. `-Wall`

is a large set of warnings that will help you satisfy many of the the code style requirements. However, `-Wall`

doesn't warn about using tabs instead of spaces (as the style guide requires), so we enable that with `-fwarn-tabs`

. Finally, `-Wall`

includes one warning we don't want, so we disable that warning with `-fno-warn-type-defaults`

.

When you are finished with the assignment, you should add the option `-Werror`

, which turns all warnings into errors, to the line above. **We will not grade your assignment if there are any compiler warnings.**

The next directive, below, suppresses the import of the `Prelude`

, the set of builtin functions that are automatically available for all Haskell programs. We're going to be writing some of these functions ourselves, so they shouldn't be automatically imported. We will only do this suppression for this particular homework assignment, in future assignments, you are encouraged to use any function in the prelude or standard library.

`{-# LANGUAGE NoImplicitPrelude #-}`

Next, we declare that we are creating a module called `Main`

and using functions defined in the modules `Prelude`

, `Test.HUnit`

and `Control.Applicative`

. The `Prelude`

line imports all but the four functions listed (which you will write), the `Test.HUnit`

line imports all functions, and the `Control.Applicative`

only imports the listed function.

```
module Main where
import Prelude hiding (all, reverse, takeWhile, zip)
import Test.HUnit
import Control.Applicative ((<*>))
```

The main program for this assignment merely runs the tests for each homework problem. You should not edit this code. Instead, your goal is to modify the problems below so that all of the tests pass. Note that the definitions in Haskell modules do not need to come in any particular order. The main function uses `test0`

, `test1`

, etc, even though their definitions are later in the file.

```
main :: IO ()
main = do
_ <- runTestTT $ TestList [ test0, test1, test2, test3, test4 ]
return ()
```

Now that we have the preliminaries out of the way, we can start the actual problems.

## Problem 0

All of the following Haskell code does what it is supposed to do (i.e. the tests pass), but it is difficult to read. Rewrite the following expressions so that they follow the style guide. (You don't need to rewrite the Test following each problem.)

```
-- Part 0 (a)
abc x y z =
if x then if y then True else
if (x && z) then True else False
else False
t0a :: Test
t0a = "0a1" ~: TestList [abc True False True ~?= True,
abc True False False ~?= False,
abc False True True ~?= False]
```

```
-- 0 (b)
arithmetic :: ((Int, Int), Int) -> ((Int,Int), Int) -> (Int, Int, Int)
arithmetic x1 x2 =
let a = fst (fst x1) in
let b = snd (fst x1) in
let c = snd x1 in
let d = fst (fst x2) in
let e = snd (fst x2) in
let f = snd x2
in
((((((b*f) - (c*e)), ((c*
d) - (a*f)
), ((a*e)-(b*d))))))
```

```
t0b :: Test
t0b = "0b" ~: TestList[ arithmetic ((1,2),3) ((4,5),6) ~?= (-3,6,-3),
arithmetic ((3,2),1) ((4,5),6) ~?= (7,-14,7) ]
```

```
-- 0 (c)
cmax :: [Int] -> Int -> Int
cmax l t
= g (length l - 1) t
where g n t = if n < 0 then t else
if (l !! n) > t then g (n-1) (l !! n) else g (n-1) t
```

```
t0c :: Test
t0c ="0c" ~: TestList[ cmax [1,4,2] 0 ~?= 4,
cmax [] 0 ~?= 0,
cmax [5,1,5] 0 ~?= 5 ]
```

```
-- 0 (d)
reverse l = reverse_aux l [] where
reverse_aux l acc =
if null l then acc
else reverse_aux (tail l) (head l : acc)
```

```
t0d :: Test
t0d = "0d" ~: TestList [reverse [3,2,1] ~?= [1,2,3],
reverse [1] ~?= [1] ]
```

```
test0 :: Test
test0 = "test0" ~: TestList [ t0a , t0b, t0c, t0d ]
```

## Bowling Game Kata

`-- Problem 1`

A Code Kata is an exercise that helps an experienced programmer hone their skills. The coding exercise is usually not difficult---what is important is the analysis and design of the problem as well and the practice and repetition that lead to good coding habits.

The Bowling Game Kata is a design exercise used to teach test-driven development to programmers in Object-Oriented languages. The powerpoint slides here go through a Java development of this problem. However, I've found that this Kata works equally well in Haskell. As you work through the problem below, compare it to the Java version.

The goal of this problem is to write a function that calculates the score of a bowling game. The function `score`

should take a list of rolls of one particular player, and calculate his or her total score.

` score :: [ Int ] -> Int `

If you are unfamiliar with the scoring rules of Ten-pin bowling, please see the ppt slides above or wikipedia.

The point of this "Kata" is to use test cases to drive the development of the score function. Therefore, this problem has several steps, interleaving the writing of test cases with refactoring the solution. This problem is a *design exercise*---TDD may seem a bit of overkill for this problem, but pay attention to the details. Each step should only add one bit of complexity, and the presence of the test cases means that we can check that we haven't broken any of that complexity as we add to the solution. In particular, as you do the exercise below, follow the rules of TDD.

TDD means write simple test cases first, get them to pass, then write slightly more complicated test cases, get them to pass, etc. For example, let's start with an extremely simple test case for the scoring function.

```
bowlingTest0 :: ([ Int ] -> Int) -> Test
bowlingTest0 score = "gutter ball" ~: 0 ~=? score (replicate 20 0)
```

If we roll 20 gutter balls in a row, our score is sadly 0. Now, we can write a *simple* scoring function that passes this test:

```
score0 :: [ Int ] -> Int
score0 _ = 0
```

We can run this test with the command:

`*Main> runTestTT (bowlingTest0 score0)`

It passes, so the result is:

```
Cases: 1 Tried: 1 Errors: 0 Failures: 0`
Counts {cases = 1, tried = 1, errors = 0, failures = 0}
```

Note that we are using higher-order programming here---the scoring function is an argument to the test case, so that we can use this test with all of the scoring functions we write.

That's easy enough. The next (baby) step in the development of the score function is to write a test case that doesn't pass. The next simplest case is one where some pins actually do get knocked down. This test models a game where someone knocks down exactly one pin with each throw. There are ten frames in a game (assuming no strikes or spares), and each frame has two throws so that is twenty throws. (The `replicate`

function is part of Haskell's standard library, called the Prelude. Unless we say otherwise, you can use any of these functions in your answers.)

```
bowlingTest1 :: ([ Int ] -> Int) -> Test
bowlingTest1 score =
"allOnes" ~: 20 ~=? score (replicate 20 1)
```

As expected, this test case doesn't pass:

```
*Main> runTestTT (bowlingTest1 score0)
### Failure in: allOnes
expected: 20
but got: 0
Cases: 1 Tried: 1 Errors: 0 Failures: 1
Counts {cases = 1, tried = 1, errors = 0, failures = 1}
```

Therefore, for the next version, implement `score1`

so that it passes *both* tests. Don't get ahead of yourself. This implementation should be the simplest function that you can think of that passes bowlingTest0 and bowlingTest1. (It *shoundn't* pass any tests with strikes or spares.)

```
score1 :: [ Int ] -> Int
score1 = score where
score _ = 0
```

Now, write a simple test case that includes a spare (i.e. a frame where the two throws add up to 10). In that case, the player gets a *bonus* of the next throw

added to his/her score. This test should fail for both score0 and score1.

```
bowlingTest2 :: ([ Int ] -> Int) -> Test
bowlingTest2 _ = "always fail" ~: assertFailure "add a test case"
```

After you have verified that `score1`

indeed fail this test:

` *Main> runTestTT (TestList [bowlingTest0 score1, bowlingTest1 score1, bowlingTest2 score1])`

rewrite score below so that it passes all three tests.

```
score2 :: [ Int ] -> Int
score2 = score where
score _ = 0
```

After you have rewritten the code, think about your solution. Is it clear? Easy to read? Can you refactor it so the logic of the game is more obvious? Can you share some of the computation between the different parts? The refactored code should behave exactly the same as `score2`

, just have better style.

Usually, you would just replace `score2`

with your new version, but call it `score2a`

below so that we can see your progress.

```
score2a :: [ Int ] -> Int
score2a = score where
score _ = 0
```

Now write another test case, perhaps with a strike in the first frame. This one should fail for all of our existing scoring functions, `score0`

, `score1`

and `score2`

.

```
bowlingTest3 :: ([ Int ] -> Int) -> Test
bowlingTest3 _ = "always fail" ~: assertFailure "add a test case"
```

```
score3 :: [ Int ] -> Int
score3 = score where
score _ = 0
```

The final test is for a perfect game. Again, this test should fail for the previous versions of `score`

. If it passes already, think of simpler test cases and simpler implementations.

```
bowlingTest4 :: ([ Int ] -> Int) -> Test
bowlingTest4 score = "perfect game" ~: 300 ~=? score (replicate 12 10)
```

Check to make sure that it fails. (The test cases can fail or trigger errors. Either way, they shouldn't pass.)

`Main*> runTestTT (TestList [bowlingTest4 score0, bowlingTest4 score1, bowlingTest4 score2, bowlingTest4 score3])`

Finally, make a version of `score`

that passes all tests above. Remember, shorter is not necessarily better. The goal is to make your code readable so that it is 'obviously' correct.

```
score4 :: [ Int ] -> Int
score4 = score where
score _ = 0
```

This test below summarizes the above---it applies each test to each version, verifying that each version passes exactly one more test than the previous.

```
test1 :: Test
test1 = TestList (map checkOutput scores) where
-- the five test cases, in order
bowlingTests = [bowlingTest0, bowlingTest1, bowlingTest2,
bowlingTest3, bowlingTest4]
-- the names of the score functions, the functions themselves,
-- and the expected number of passing tests
scores = zip3 ['0' ..] [score0, score1, score2, score3, score4] [1..]
-- a way to run a unit test without printing output
testSilently = performTest (\ _ _ -> return ())
(\ _ _ _ -> return ()) (\ _ _ _ -> return ()) ()
-- run each bowling test on the given score function, making sure that
-- the expected number of tests pass.
checkOutput (name, score, pass) = " Testing score" ++ [name] ~: do
(s0,_) <- testSilently (TestList $ bowlingTests <*> [score])
assert $ pass @=? cases s0 - (errors s0 + failures s0)
```

Note that the five test cases in this problem are probably not complete. There may be versions of `score`

that pass all five of them, but are still not *correct* scoring functions. Feel free to add more tests to this problem if you would like to do better.

## Vedic Multiplication

`-- Problem 2`

Vedic Mathematics is the early stage of the Indian Mathematical heritage. In this tradition, which is based on mental arithmetic, common arithmetic functions are reformulated so that little or no intermediate results need to be written down.

One example is the algorithm for multiplication, called Ūrdhva Tiryagbhyām, which is Sanskrit for "vertically and crosswise". This algorithm computes products of numbers digit-by-digit, one digit at a time. Suppose we would like to multiply two n-digit numbers,

` x_{n-1} ... x_1 x_0 and y_{n-1} ... y_1 y_0 `

to produce the (at most) 2n digit result

` z_{2n-1} ... z_1 z_0`

We can compute each digit of the output z_k by working right-to-left, using two results: c_k, the "carry" from the previous step (initially zero), and s_k, the discrete convolution of the first k input digits (x_k ... x_0) and (y_k ... y_0).

` z_k = (s_k + c_k) mod 10`

The carry for the next step is

` c_k = (s_k + c_k) div 10`

The *discrete convolution* of two lists of numbers is the dot product of the first list and the reverse of the second list. For example, the convolution of the lists `[9,4,6]`

`[9,2,3]`

is `89`

because `89 = 9*3 + 4*2 + 6*9`

.

For example, suppose we wanted to multiply

```
9 4 6
x 9 2 3
----------
```

We compute the result digits (called `z5 z4 z3 z2 z1 z0`

) in stages. We start with the first carry `c0`

(which is `0`

), and the first convolution s0, which is:

`s0 = conv [6] [3] = 18`

From these, we can compute the rightmost digit of the output (`z0`

) and the next carry (`c1`

):

```
z0 = (s0 + c0) `mod` 10 = 8
c1 = (s0 + c0) `div` 10 = 1
```

For the next step, we compute the next convolution (of `x1 x0`

and `y1 y0`

) and use that result for the next digit of the output (`z1`

) and its carry:

```
s1 = conv [4,6] [2,3] = 24
z1 = (s1 + c1) `mod` 10 = 5
c2 = (s1 + c1) `div` 10 = 2
```

We continue as before, computing the convolution at each step and remembering the carry.

```
s2 = conv [9,4,6][9,2,3] = 89
z2 = (s2 + c2) `mod` 10 = 1
c3 = (s2 + c2) `div` 10 = 9
s3 = conv [0,9,4,6][0,9,2,3] = 54 (= conv [9,4][9,2])
z3 = (s3 + c3) `mod` 10 = 3
c4 = (s3 + c3) `div` 10 = 6
s4 = conv [0,0,9,4,6][0,0,9,2,3] = 81 (= conv [9][9])
z4 = (s4 + c4) `mod` 10 = 7
c5 = (s4 + c4) `div` 10 = 8
s5 = conv [0,0,0,9,4,6][0,0,0,9,2,3] = 0 -- will always be zero
z5 = (s5 + c5) `mod` 10 = 8 -- will always be c5
c6 = (s5 + c5) `div` 10 = 0 -- will always be zero
```

So the result of the multiplication is:

`[8,7,3,1,5,8]`

`-- 2a)`

Implement the convolution function.

```
-- | The conv function takes two lists of numbers, reverses the
-- second list, multiplies their elements together pointwise, and sums
-- the result. This function assumes that the two input
-- lists are the same length.
conv :: [Int] -> [Int] -> Int
conv _ _ = error "conv: unimplemented"
```

```
t2a :: Test
t2a = "2a" ~: conv [2,4,6] [1,2,3] ~?= 20
```

`-- 2b) `

Given two numbers, written as lists of digits, the first step of Vedic multiplication is to add extra zeros to the beginning of both lists.

```
-- | The normalize function adds extra zeros to the beginning of each
-- list so that they each have length 2n, where n is
-- the length of the longer number.
normalize :: [Int] -> [Int] -> ([Int], [Int])
normalize = error "normalize: unimplemented"
```

```
t2b :: Test
t2b = "2b" ~: normalize [1] [2,3] ~?= ([0,0,0,1], [0,0,2,3])
```

`-- 2c)`

Now use `conv`

and `normalize`

to implement the Ūrdhva Tiryagbhyām algorithm.

```
-- | multiply two numbers, expressed as lists of digits using
-- the Ūrdhva Tiryagbhyām algorithm.
multiply :: [Int] -> [Int] -> [Int]
multiply = error "unimplemented"
```

```
t2c :: Test
t2c = "2c" ~: multiply [9,4,6][9,2,3] ~?= [8,7,3,1,5,8]
```

`-- 2d) (Warning, this one is tricky!)`

Your definition of convolution above probably traverses one of the input lists multiple times. Rewrite this function so that each list is traversed *only* once. (You may assume that both lists are of the same length.)

```
convAlt :: [Int] -> [Int] -> Int
convAlt = error "convAlt: unimplemented"
```

```
t2d :: Test
t2d = "2d" ~: convAlt [2,4,6][1,2,3] ~=? 20
```

```
test2 :: Test
test2 = TestList [t2a,t2b,t2c,t2d]
```

[The inspiration for this problem comes from the paper: Olivier Danvy and Meyer Goldberg, "There and Back Again", BRICS RS-01-39]

## List library chops

`-- Problem 3`

Define, debug and test the following functions. (Some of these functions are part of the Haskell standard prelude or standard libraries like Data.List.) Their solutions are readily available online. You should *not* use these resources, and instead, implement them yourself.

For each part of the assignment, you need to declare the type of the function, define it, and replace the testcase for that part based on the problem description. The declared type of each function should be the most general one. Make sure to test the functions with multiple inputs using `TestList`

.

```
test3 :: Test
test3 = "test3" ~: TestList [t3a, t3b, t3c, t3d, t3e, t3f, t3g, t3h]
```

`-- 3 (a)`

```
-- The intersperse function takes an element and a list
-- and `intersperses' that element between the elements of the list.
-- For example,
-- intersperse ',' "abcde" == "a,b,c,d,e"
```

```
intersperse = error "unimplemented: intersperse"
t3a :: Test
t3a = "3a" ~: assertFailure "testcase for intersperse"
```

`-- 3 (b)`

```
-- invert lst returns a list with each pair reversed.
-- for example:
-- invert [("a",1),("a",2)] returns [(1,"a"),(2,"a")]
-- invert ([] :: [(Int,Char)]) returns []
-- note, you need to add a type annotation to test invert with []
--
```

```
invert = error "unimplemented: invert"
t3b :: Test
t3b = "3b" ~: assertFailure "testcase for invert"
```

`-- 3 (c)`

```
-- takeWhile, applied to a predicate p and a list xs,
-- returns the longest prefix (possibly empty) of xs of elements
-- that satisfy p:
-- For example,
-- takeWhile (< 3) [1,2,3,4,1,2,3,4] == [1,2]
-- takeWhile (< 9) [1,2,3] == [1,2,3]
-- takeWhile (< 0) [1,2,3] == []
```

```
takeWhile = error "unimplemented: takeWhile"
t3c :: Test
t3c = "3c" ~: assertFailure "testcase for takeWhile"
```

`-- 3 (d)`

```
-- find pred lst returns the first element of the list that
-- satisfies the predicate. Because no element may do so, the
-- answer is returned in a "Maybe".
-- for example:
-- find odd [0,2,3,4] returns Just 3
```

```
find = error "unimplemented: find"
t3d :: Test
t3d = "3d" ~: assertFailure "testcase for find"
```

`-- 3 (e)`

```
-- all pred lst returns False if any element of lst
-- fails to satisfy pred and True otherwise.
-- for example:
-- all odd [1,2,3] returns False
```

```
all = error "unimplemented: all"
t3e :: Test
t3e = "3e" ~: assertFailure "testcase for all"
```

`-- 3 (f)`

```
-- map2 f xs ys returns the list obtained by applying f to
-- to each pair of corresponding elements of xs and ys. If
-- one list is longer than the other, then the extra elements
-- are ignored.
-- i.e.
-- map2 f [x1, x2, ..., xn] [y1, y2, ..., yn, yn+1]
-- returns [f x1 y1, f x2 y2, ..., f xn yn]
```

`map2 = error "unimplemented: map2"`

```
t3f :: Test
t3f = "3f" ~: assertFailure "testcase for map2"
```

`-- 3 (g)`

```
-- zip takes two lists and returns a list of corresponding pairs. If
-- one input list is shorter, excess elements of the longer list are
-- discarded.
-- for example:
-- zip [1,2] [True] returns [(1,True)]
```

`zip = error "unimplemented: zip"`

```
t3g :: Test
t3g = "3g" ~: assertFailure "testcase(s) for zip"
```

`-- 3 (h) WARNING this one is tricky!`

```
-- The transpose function transposes the rows and columns of its argument.
-- If the inner lists are not all the same length, then the extra elements
-- are ignored.
-- for example:
-- transpose [[1,2,3],[4,5,6]] returns [[1,4],[2,5],[3,6]]
```

`transpose = error "unimplemented: transpose"`

```
t3h :: Test
t3h = "3h" ~: assertFailure "testcase for transpose"
```

## Longest Common Subsequence

`-- Problem 4`

This last problem is a challenge problem. You *do not* need to solve it to get full credit on the assignment.

Define the function

```
lcs :: String -> String -> String
lcs = error "unimplemented: lcs"
```

which computes the longest common subsequence of its two arguments. The longest common subsequence is the longest a sequence of characters that occurs, in the same order, in both of the arguments.

For example,

```
test4 :: Test
test4 = "4" ~: TestList [ lcs "Advanced" "Advantaged" ~?= "Advaned" ]
```

The longest common subsequence may not be unique. For example, your implementation will satisfy only one of the following tests. Either is correct.

```
test4a :: Test
test4a = "4a" ~: lcs "abcd" "acbd" ~?= "acd"
```

```
test4b :: Test
test4b = "4b" ~: lcs "abcd" "acbd" ~?= "abd"
```

There are several ways to approach this problem, and some of them are more efficient than others. Even if your tests pass the problems above, think about other ways to solve this problem. In particular, think about memoization and optimizing the cases where the beginning and the ends of the two strings match.

If you are rusty on your algorithms, the wikipedia page for longest common subsequence may be useful. The simple, exponential solution is an intermediate problem. Optimizing this solution is more challenging.

## News :

Welcome to CIS 552!

See the home page for basic
information about the course, the schedule for the lecture notes
and assignments, the resources for links to the required software
and online references, and the syllabus for detailed information about
the course policies.