Type-checked Bits

The bit processing functions you wrote for the previous Haskell assignment were just lists of Int values. It was up to the programmer using those functions to make sure they only put 0s and 1s on those lists.

Another way to write those sorts of this functions is to declare a bit data type like this:

data Bit = Zero | Onederiving (Show, Eq)

The deriving (Show, Eq) line enables a Bit to be printed (e.g. in the interpreter), and to be used with == and /= .

Please implement the following functions:

1. (1 mark) Implement flipBit :: Bit -> Bit , which changes a Zero to a One , and vice-versa. For example:

   > flipBit ZeroOne> flipBit OneZero

   Do not use recursion in your answer.

2. (1 mark) Implement invert :: [Bit] -> [Bit] , which flips all the bits in the input list. For example:

   > invert [][]> invert [Zero, Zero, One, Zero][One, One, Zero, One]

   Do not use recursion in your answer.

3. (2 marks) Implement all_bit_seqs n , which returns a list of Bit lists representing all possible bit sequences of length n. You can assume n > 0. For example:

   > all_bit_seqs 1[[Zero],[One]]> all_bit_seqs 2[[Zero,Zero],[Zero,One],[One,Zero],[One,One]]> all_bit_seqs 3[[Zero,Zero,Zero],[Zero,Zero,One],[Zero,One,Zero],[Zero,One,One], [One,Zero,Zero],[One,Zero,One],[One,One,Zero],[One,One,One]]> take 2 (all_bit_seqs 25)[[Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero, Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero], [Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero, Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,Zero,One]]

   1 mark will be for correctly implementing all_bit_seqs , and 1 mark will be for not using recursion in your answer.

4. (1 mark) Implement bitSum1 :: [Bit] -> Int , which returns the sum of the bits in the input where Zero is 0, and One is 1. For example:

   > bitSum1 []0> bitSum1 [One]1> bitSum1 [One, One]2> bitSum1 [One, One, Zero]2> bitSum1 [One, One, Zero, One, One]4> bitSum1 (replicate 4 One)4

   Do not use recursion in your answer.

5. (1 mark) Implement bitSum2 :: [Maybe Bit] -> Int , which returns the sum of the maybe-bits in the input, i.e. Zero is 0, One is 1, and Nothing is 0. For example:

   > bitSum2 []0> bitSum2 [Nothing]0> bitSum2 [Nothing, Nothing, Just One]1> bitSum2 [Nothing, Nothing, Just One, Just Zero, Just One]2

   You may use recursion in your answer!

A Custom List Data Type

Haskell has good built-in support for lists that you should use for most projects. But here, the problem is to write some basic list processing functions using this custom data type:

data List a = Empty | Cons a (List a)deriving Show

This is an algebraic data type. It defines a type called List a , that represents a list of 0, or more, objects of any type a . A List a is either Empty , or it is of the form (Cons first rest) , where first is of type a , and rest is of type List a . This mimics the common cons cell implementation of a singly linked list.

The line deriving Show is added as a convenience: it tells Haskell how to print a List a in the interpreter.

Implement the following functions:

6. (1 mark) Implement toList :: [a] -> List a , which converts a regular Haskell list to a List a . For example:

   > toList []Empty> toList [2, 7, 4]Cons 2 (Cons 7 (Cons 4 Empty))> toList "apple"Cons 'a' (Cons 'p' (Cons 'p' (Cons 'l' (Cons 'e' Empty))))

7. (1 mark) Implement toHaskellList :: List a -> [a] , which converts a List a to a regular Haskell list. For example:

   > toHaskellList Empty[]> toHaskellList (Cons 2 (Cons 7 (Cons 4 Empty)))[2,7,4]> toHaskellList (Cons "cat" (Cons "bat" (Cons "rat" Empty)))["cat","bat","rat"]

For the following functions, dont use toList or toHaskellList in your implementations; use them just for testing and debugging. Stick tp basic recursion and Haskell prelude functions for your solution code.

Make sure to include the most general type signatures for each of the functions.

8. (1 mark) Implement append A B , where A and B are both of type List a , that returns a new List a that consists of all the elements of A followed by all the elements of B . In other words, it does for List a what ++ does for regular Haskell lists. For example:

   > append (Cons 1 (Cons 2 (Cons 3 Empty))) (Cons 7 (Cons 8 Empty))Cons 1 (Cons 2 (Cons 3 (Cons 7 (Cons 8 Empty))))

9. (1 mark) Implement the function removeAll f L , where f is a predicate of type a -> Bool and L is of type List a , that returns a List a that is the same as L but all items satisfying f (i.e. for which f returns True ) have been removed.

   For example:

   > removeAll even EmptyEmpty> removeAll (x -> x == 'b') (Cons 'b' (Cons 'u' (Cons 'b' Empty)))Cons 'u' Empty> removeAll even (Cons 1 (Cons 2 (Cons 3 (Cons 4 Empty))))Cons 1 (Cons 3 Empty)> removeAll odd (Cons 1 (Cons 2 (Cons 3 (Cons 4 Empty))))Cons 2 (Cons 4 Empty)

10. (1 mark) Implement the function sort L , where L has type List a , that returns a new List a equal to L in ascending order. Use either quicksort or mergesort.

    It must have this type signature:

    sort :: Ord a => List a -> List a

    Ord a => means that the type a must be usable with comparisons functions such as < , <= , == , etc.

    For example:

    > sort EmptyEmpty> sort (Cons 'c' (Cons 'a' (Cons 'r' (Cons 't' Empty))))Cons 'a' (Cons 'c' (Cons 'r' (Cons 't' Empty)))

Best Partition of a Set of Integers

Suppose S S is a finite, non-empty set of Int s such that 1 | S | 15 1|S|15 ( | S | |S| is the cardinality of S S , i.e. the number of elements in | S | |S| ). A partition of S S consists of two sets, A A and B B , such that S = A B S=AB and A B = AB= .

The score of a partition is a b s ( s u m ( A ) s u m ( B ) ) abs(sum(A)sum(B)) . Partitions with a score of 0 are called perfect partitions . Not every set S S has a perfect partition, but there is always at least one best partition , i.e. a partition of S S with the lowest possible score. For example, S = { 1 , 2 , 4 } S={1,2,4} has no perfect partition, although A = { 4 } , B = { 1 , 2 } A={4},B={1,2} is a best partition for it. Its quite possible for a set to have multiple different best partitions.

11. (3 marks) Write a Haskell function called best_partition :: [Int] -> (Int, [Int], [Int]) that returns a best partition of a list of unique Int s. The return value is a 3-tuple of type (Int, [Int], [Int]) that can be informally defined like this:

    best_partition S S returns the 3-tuple ( a b s ( s u m ( A ) s u m ( B ) ) , A , B ) (abs(sum(A)sum(B)),A,B)

    Also, it is required that the elements of both the returned A A and B B be in ascending sorted order.

    Importantly, you should assume that the input list S is non-empty and has, at most, 15 elements. Youre function doesnt need to check for this it will only be tested on lists that meet this pre-condition.

    Make sure best_partition always returns a best partition, and not just an approximation of a best partition. Since the input list can have at most 15 elements, brute force is a reasonable approach.

    Here are some examples. Keep in mind that there may be more than one best partition, and so the results shown here are not necessarily the only possible correct outputs:

    > best_partition [7](7,[],[7])> best_partition [7, 4](3,[4],[7])> best_partition [7, 4, 3](0,[3,4],[7])> best_partition [7, 4, 3, 6](0,[4,6],[3,7])> best_partition [7, 4, 3, 6, 10](2,[6,10],[3,4,7])> best_partition [1..10](1,[8,9,10],[1,2,3,4,5,6,7])> best_partition [4..10](1,[7,8,10],[4,5,6,9])> best_partition [2,3,5,7,11,13,17](0,[5,11,13],[2,3,7,17])