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, download the zipfile, edit Main.hs (this file contains just the code) and submit it through the course web page.

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 for GHC (these are specific instructions for the compiler). GHC doesn't warn about these behaviors automatically, but they are required by the style guide so you want to know about them.

> {-# OPTIONS -fwarn-incomplete-patterns -fwarn-tabs -fno-warn-type-defaults #-}

This next compiler option

> {-# OPTIONS -fdefer-type-errors  #-}

turns type errors into warnings so that you can still run your code in ghci even if it doesn't type check. This flag doesn't defer all compile-time errors (such as errors for unbound variables) and you definitely should fix your type errors. However, having it in place helps make development more interactive. Of course, if you try to run the part of your code with a type error in it, it will fail.

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.

Next, we declare that we are creating a module called Main and using functions defined in the modules Prelude, Test.HUnit, Data.List and Data.Char.

The Prelude line imports all except for the functions listed (which you will write). The module Prelude is special in that it is always imported by default, so the the point of this line is not to import more functions, but rather to exclude a few funtions. (Haskell does not allow functions to be redefined in the same module.)

The Test.HUnit line imports all functions defined in that module. The line Data.List imports all functions from that module, but makes them available as List.intersperse, etc.

> module Main where
> import Prelude hiding (takeWhile, all, zip, reverse, concat)
> import Test.HUnit
> import qualified Data.List as List
> import qualified Data.Char as Char
> import qualified Data.Maybe as Maybe
> import qualified Text.Read as Read

The main "program" for this assignment runs the tests for each homework problem below. You should not edit this definition. 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; here, the main function uses testStyle, testLists, etc, even though their definitions come later in the file.

> main :: IO ()
> main = do
>    _ <- runTestTT $ TestList [ testStyle,
>                                testLists,
>                                testWeather,
>                                testSoccer ]
>    return ()

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

> --------------------------------------------------------------------------------

Problem (Good Style)

> testStyle :: Test
> testStyle = "testStyle" ~:
>    TestList [ tabc , tarithmetic, treverse, tzip ]

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 exactly follow the style guide. Be careful: the style guide includes quite a few rules, and we've broken most of them in what follows! (You don't need to rewrite the Test following each part, but you do need to make sure that you don't break the code as you refactor it!)

NOTE: do not change the name of any of the declarations below. We will be using automatic testing to ensure that you do not change their functionality.

> abc x y z =
>   if x then if y then True else
> 	 if (x && z) then True else False
>   else False

> tabc :: Test
> tabc = "abc" ~: TestList [abc True False True ~?= True,
>                           abc True False False ~?= False,
>                           abc False True True ~?= False]

> 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))))))

> tarithmetic :: Test
> tarithmetic = "arithmetic" ~:
>    TestList[ arithmetic ((1,2),3) ((4,5),6) ~?= (-3,6,-3),
>              arithmetic ((3,2),1) ((4,5),6) ~?= (7,-14,7) ]

> reverse l  = reverse_aux l [] where
>   reverse_aux l acc =
>     if null l then acc
>        else reverse_aux (tail l) (head l : acc)

> treverse :: Test
> treverse = "reverse" ~: TestList [reverse [3,2,1] ~?= [1,2,3],
>                                   reverse [1]     ~?= [1] ]

> zip xs ys = g 0 xs ys where
>   g n xs ys = if n == length xs || n == length ys then [] else
>           (xs !! n, ys !! n) : g (n + 1) xs ys

> tzip :: Test
> tzip = "zip" ~:
>   TestList [ zip "abc" [True,False,True] ~?= [('a',True),('b',False), ('c', True)],
>              zip "abc" [True] ~?= [('a', True)],
>              zip [] [] ~?= ([] :: [(Int,Int)]) ]

> --------------------------------------------------------------------------------

Problem (List library chops)

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 look for these solutions: 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 each of these functions with multiple inputs using TestList. We will be grading your test cases as well as the correctness and style of your solutions!

> testLists :: Test
> testLists = "testLists" ~: TestList
>   [tintersperse, tinvert, ttranspose, tconcat, tcountSub]

> -- 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 is defined in Data.List, and you can test your solution against
> -- that one.

> intersperse = undefined

> tintersperse :: Test
> tintersperse = "intersperse" ~: (assertFailure "testcase for intersperse" :: Assertion)

> -- 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 = undefined

> tinvert :: Test
> tinvert = "invert" ~: (assertFailure "testcase for invert" :: Assertion)

> -- concat

> -- The concatenation of all of the elements of a list of lists
> -- for example:
> --    concat [[1,2,3],[4,5,6],[7,8,9]] returns [1,2,3,4,5,6,7,8,9]
> --
> -- NOTE: remember you cannot use any functions from the Prelude or Data.List for
> -- this problem, even for use as a helper function.

> concat = undefined

> tconcat :: Test
> tconcat = "concat" ~: (assertFailure "testcase for concat" :: Assertion)

> -- transpose  (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. Note, this is *not* the same behavior as the library version
> -- of transpose.

> -- for example:
> --    transpose [[1,2,3],[4,5,6]] returns [[1,4],[2,5],[3,6]]
> --    transpose  [[1,2],[3,4,5]] returns [[1,3],[2,4]]
> --    transpose  [[]] returns []
> -- transpose is defined in Data.List

> transpose = undefined

> ttranspose :: Test
> ttranspose = "transpose" ~: (assertFailure "testcase for transpose" :: Assertion)

> -- countSub sub str

> -- Return the number of (potentially overlapping) occurrences of substring sub
> -- found in the string str.
> -- for example:
> --      countSub "aa" "aaa" returns 2

> countSub = undefined
> tcountSub :: Test
> tcountSub = "countSub" ~: (assertFailure "testcase for countSub" :: Assertion)

> --------------------------------------------------------------------------------

Data Munging Kata

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. This exercise comes from website devoted to Code Katas and is not specific to Haskell.

Unlike the exercises above, for this problem you are allowed to use functions from Haskell's standard libraries. In particular, you may use list functions from the Prelude, or from Data.List in your solution. You may also use functions from Data.Char.

This problem is an exercise in three parts to do with real world data. For that reason, we aren't expecting you to produce a robust solution. Your code must work only for the input test files that we provide. We won't test it on any other inputs! Consequently, you can ignore the style guideline that says that your functions must not be partial...

This problem also is about refactoring, so try hard not to read ahead—-do each of the three parts below in turn and then reflect on your experience.

> -- Part One: Hottest Day

In jul17.dat (in the zipfile) you’ll find daily weather data for Philadelphia, PA NJ for July 2017. This data is taken from NOAA.

Download this text file, then write a program to output the day number (column one) with the smallest temperature spread (the maximum temperature is the second column, the minimum the third column).

We've given you the I/O parts of the program --- opening the file and then printing the final result. Your job is to write the weather function below, that takes the string containing the text of the file and processes it to find the answer.

> weather :: String -> String
> weather str = error "unimplemented"

> weatherProgram :: IO ()
> weatherProgram = do
>   str <- readFile "jul17.dat"
>   putStrLn (weather str)

The (overloaded) Read.readMaybe function can help you convert strings into integers. We've given it a new name and type signature to make it easier to use.

> readInt :: String -> Maybe Int
> readInt = Read.readMaybe

Here is the test case for this part. If this test fails because it cannot find the input file, you need to use the :cd command in ghci to make sure that you are in the right directory.

> testWeather :: Test
> testWeather = "weather" ~: do str <- readFile "jul17.dat"
>                               weather str @?= "6"

> --------

> -- Part Two: Soccer League Table

The file soccer.dat contains the results from the English Premier League for 2001/2. The columns labeled ‘F’ and ‘A’ contain the total number of goals scored for and against each team in that season (so Arsenal scored 79 goals against opponents, and had 36 goals scored against them). Write a program to print the name of the team with the smallest (absolute) difference in ‘for’ and ‘against’ goals.

Your program needs to only work with the soccer.dat file. If given a different file it may or may not throw an error.

> soccer :: String -> String
> soccer = error "unimplemented"

> soccerProgram :: IO ()
> soccerProgram = do
>   str <- readFile "soccer.dat"
>   putStrLn (soccer str)

> testSoccer :: Test
> testSoccer = "soccer" ~: do
>   str <- readFile "soccer.dat"
>   soccer str @?= "Aston_Villa"

> -- Part Three: DRY Fusion

Now, take the two programs written previously and factor out as much common code as possible, leaving you with two smaller programs and some kind of shared functionality.

> weather2 :: String -> String
> weather2 = undefined

> soccer2 :: String -> String
> soccer2 = undefined

> -- Kata Questions

Fill in the strings below with your answers.

> -- To what extent did the design decisions you made when writing the original
> -- programs make it easier or harder to factor out common code?

> shortAnswer1 :: String
> shortAnswer1 = "Fill in your answer here"

> -- Was the way you wrote the second program influenced by writing the first?

> shortAnswer2 :: String
> shortAnswer2 = "Fill in your answer here"

> -- Is factoring out as much common code as possible always a good thing? Did the
> -- readability of the programs suffer because of this requirement? How about the
> -- maintainability?

> shortAnswer3 :: String
> shortAnswer3 = "Fill in your answer here"

CIS 552: Advanced Programming

Fall 2017

HW 1 - Haskell List Processing and recursion

Problem (Good Style)

Problem (List library chops)

Data Munging Kata