haskell-21

Instructions

Due: November 22 11:59 pm

Please read the following instructions carefully:

  1. You will find the files src/HaskellOne.hs with many definitions left as undefined. You need to fill them in as described in this README.
  2. You will find the file test/Spec.hs with some tests. Add additional tests as you see fit. You should make sure that your code passes all the tests by running stack test. Also remember, that stack ghci is your friend.
  3. You will not be penalized for warnings generated by the compiler. You can even turn off the warnings if you want. But we suggest you pay attention to them.
  4. You may not import any libraries. Ask course staff if you have a reason to do so. On the other hand, you are encouraged to use the combinators in the Prelude (i.e, the built-in functions).
  5. All top-level definitions should have a type-annotation even if Haskell does not require it explicitly. Also, you may not alter the type signatures of definitions already provided.
  6. Do not alter the directory structure of the project, or change the file names or module names.

Problem 1

  1. (10 points) Define the function smooth2 :: Frac a => [a] -> [a]. (This just denotes that you are using some type on which division makes sense, like Float or Double.) The 2-smoothening of a sequence is defined as the avergage of every two consecutive elements.
  2. (5 points) You can claim the additional 5 points if your function does not explicitly use pattern matching on the input list. There is no need to give two definitions. The slick definition is sufficient.

As an hint for part 2, you may want to use the combinators zipWith and tail (and a lambda function).

Problem 2

  1. (10 points) Define the function kestrel :: p -> q -> p. Any definition (other than undefined or error _) will do. No tests are needed.
  2. (Extra Credit: 15 pts) Define the function starling :: (p -> q -> r) -> (p -> q) -> p -> r. Any definition (other than undefined or error _) will do. No tests are needed.

Problem 3 (25 pts)

Define the function kLargest :: Ord a => Int -> [a] -> [a] such that kLargest k xs is a list of k elements of xs in increasing order. You may assume that k <= length xs.

Problem 4

Consider the data type data InfBinTree a = Fork a (InfBinTree a) (InfBinTree a) of infinite binary trees. Further, consider root (Fork a _ _) = a.

  1. (15 pts) Define the function treeRepeat :: a -> InfBinTree a where treeRepeat x defines the tree which has x at every node. You can see the test/Spec.hs file for a hint.

Even if we assume that we have a type on which equality makes sense, we cannot define a (computable) notion of equality among InfBinTree since these trees are infinite and we cannot check every node.

  1. (25 pts) Implement instead boundedEq :: Eq a => Int -> InfBinTree a -> InfBinTree a -> Bool so that boundedEq n t1 t2 is True if the two trees consist of equal values in every node in the first n levels. Make sure that boundedEq 0 x y = True for any x, y.

  2. (10 pts) Define two trees xTree, yTree :: InfBinTree Int such that boundedEq 0 xTree yTree = True, boundedEq 1 xTree yTree = True but for n > 1, boundedEq n xTree yTree = False.

  3. (Extra Credit: 25 pts) Define treeBfs :: InfBinTree a -> [a] so that it converts an infinite tree into an infinite list by doing a breadth first search on it.

As a hint, you may want to define an auxilary function collect :: [InfBinTree a] -> [a] which behaves in the following way: In order to evaluate collect [t1, t2, t3, t4], it first extracts (root t1), (root t2), (root t3), (root t4), then it considers collect [(left t1), (right t1), (left t2), (right t2), (left t3), (right t3), (left t4), (right t4)].