Problem Set 3: Haskell

The following questions are meant as practice for learning some basic features of Haskell. Submit all your solutions in a single file named ps3.hs.

Questions

Important: Include the most general type signature at the top of each function. Your code will be marked as wrong if the type signature is missing or incorrect!

1. (1 mark) Write a function called is_bit x that returns True when x is 0 or 1, and False otherwise.

   Assume x is of type Int, and the type of the returned value is Bool.

2. (1 mark) Write a function called flip_bit x that returns 1 if x is 0, and 0 if x is 1. If x is not a bit, then call error msg, where msg is a helpful error message string.

   Assume x is of type Int, and the type of the returned value is also Int.

3. In each of the following functions, x is a list of Int values, and the returned value has type Bool.

   1. (1 mark) Write a function called is_bit_seq1 x that returns True if x is the empty list, or if it contains only bits (as determined by is_bit).

      Use recursion and guarded commands in your solution.

   2. (1 mark) Re-do the previous question, except this time name the function is_bit_seq2 x, and use recursion and at least one if-then-else expression in your solution. Don’t use any guarded commands.

   3. (1 mark) Re-do the previous question, except this time name the function is_bit_seq3 x, and use the all function in your solution. Don’t use recursion, guarded commands, or if-then-else.

4. In each of the following functions, x a list of Int values, and the type the returned value is also a list of Int.

   1. (1 mark) Write a function called invert_bits1 x that returns a sequence of bits that is the same as x, except 0s become 1s and 1s become 0s. For example, invert_bits1 [0,1,1,0] returns [1,0,0,1].

      Use basic recursion in your solution.

   2. (1 mark) Re-do the previous question, but name the function invert_bits2 x, and it implement it using the map function (and no recursion).

   3. (1 mark) Re-do the previous question, but name the function invert_bits3 x, and it implement it using a list comprehension (and no recursion, and no map function).

5. (1 mark) Write a function called bit_count x that returns a pair of values indicating the number of 0s and 1s in x. For example, bit_count [1,1,0,1] returns the pair (1, 3).

   Assume x is a list of Int values, and only contains bits. The type of the returned value is (Int, Int).

6. (1 mark) Write a function called all_bit_seqs n that returns a list of all bit sequences of length n. The order of the sequences doesn’t matter. If n is less than 1, then return an empty list.

   Assume n is an Int, and the returned value is a list of Int lists.