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 | One
    deriving (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 Zero
   One
   
   > flipBit One
   Zero
   

   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, don’t 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 Empty
   Empty
   
   > 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 Empty
    Empty
    
    > 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 SS is a finite, non-empty set of Ints such that 1≤|S|≤151≤|S|≤15 (|S||S| is the cardinality of SS, i.e. the number of elements in |S||S|). A partition of SS consists of two sets, AA and BB, such that S=A∪BS=A∪B and A∩B=∅A∩B=∅.

The score of a partition is abs(sum(A)−sum(B))abs(sum(A)−sum(B)). Partitions with a score of 0 are called perfect partitions. Not every set SS has a perfect partition, but there is always at least one best partition, i.e. a partition of SS 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. It’s 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 Ints. The return value is a 3-tuple of type (Int, [Int], [Int]) that can be informally defined like this:

    best_partition SS returns the 3-tuple (abs(sum(A)−sum(B)),A,B)(abs(sum(A)−sum(B)),A,B)

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

    Importantly, you should assume that the input list S is non-empty and has, at most, 15 elements. You’re function doesn’t 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])
    

    Note that the elements of the returned partition lists are in ascending sorted order.