Haskell Project¶

For all of the following functions, please follow these rules:

Don’t import any Haskell modules. Use only the functions from the standard prelude. You can write helper functions as long as they use only standard prelude functions.
Figure out these problems yourself. Try not to use any substantial code that originates from books, websites or other people. If you do, please cite the source of the code.
If a type signature is not given in a question, then include the most general type signature for each function you write. It may be necessary to use type classes.
Don’t change the names (or types) of any of the functions — otherwise the marking software will give you 0!
Please format your code perfectly, and use source code comments to explain any tricky or confusing parts. Code that is very difficult to read may lose marks.

Please put all your code in a single file named proj3.hs.

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 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.
(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.

(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.

(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.

(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:

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

(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.

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

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

(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 $S$ is a finite, non-empty set of Ints such that $1 \leq | S | \leq 15$ ( $| S |$ is the cardinality of $S$ , i.e. the number of elements in $| S |$ ). A partition of $S$ consists of two sets, $A$ and $B$ , such that $S = A \cup B$ and $A \cap B = \emptyset$ .

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

(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 $S$ returns the 3-tuple $(a b s (s u m (A) - s u m (B)), A, B)$

Also, it is required that the elements of both the returned $A$ and $B$ 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])
```

Haskell Project¶

Type-checked Bits¶

A Custom List Data Type¶

Best Partition of a Set of Integers¶

Related Posts