Assignment 3: Haskell

For this assignment, 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.

  The one exception is QuickTest: you can use that to help test your functions. Indeed, you are strongly encouraged to use it!

• If a type signature is not given in a question, then include the most general correct type signature for each function you write. It may be necessary to use type classes for some signatures.

• Don’t change the names (or types) of any of the functions — otherwise the marking software may give you 0!

• Figure out these problems yourself. Don’t use any substantial code that originates from books, websites or other people. If you do, you must cite the source of the code or ideas.

• You don’t need to do any substantial error-checking (unless a question specifically says you should). You can assume obvious pre-conditions hold for inputs.

• Please format your code beautifully and consistently, and use source code comments to explain any tricky or confusing parts. Code that is very difficult to read may lose marks.

When it is time to submit your work, please put all your functions into a file named a3.hs and submit it on Canvas.

Basic Functions

1. (1 mark) The function snoc x lst returns a new list that is the same as lst, except x has been added to the end of it. It has this signature:

   snoc :: a -> [a] -> [a]
   

   For example, snoc 5 [1,2,3] returns [1,2,3,5], and snoc 's' "cat" returns "cats".

   Implement snoc using only basic recursion. Do not use ++ or reverse or any other such high-level functions.

2. (1 mark) Write your own version of the Haskell append operator ++ with this signature:

   myappend :: [a] -> [a] -> [a]
   

   Of course, don’t use functions like ++ or concat in your answer.

3. (1 mark) Write your own version of reverse with this signature:

   myreverse :: [a] -> [a]
   

   Don’t use any non-trivial functions in your answer unless you write those functions yourself.

4. (1 mark) Write a function called count_emirps n that returns the number of emirps less than, or equal to, n.

   An emirp is a prime number that is a different prime when its digits are reversed. For example, 107 is an emirp because 107 is prime, and its reverse, 701, is a different prime. However, 7 and 101 are not emirps because while their reverses are primes, they are not different primes.

   The first few emirps are: 13, 17, 31, 37, 71, 73, ….

   count_emirps has this signature:

   count_emirps :: Int -> Int
   

   For example, count_emirps 100 returns 8, and count_emirps 1000 returns 36. If n is less than 13, count_emirps n returns 0.

5. (1 mark) Write a function called biggest_sum that takes a list of one, or more, integer lists as input, and returns the list with the greatest sum. It has this signature:

   biggest_sum :: [[Int]] -> [Int]
   

   For example, biggest_sum [[2,5], [-1,3,4], [2]] returns [2,5].

   You can assume the list passed to biggest_sum is non-empty.

   If one, or more more, lists are tied for the biggest sum, then return the first one.

6. (1 mark) Write a function called greatest, which has the following signature:

   greatest :: (a -> Int) -> [a] -> a
   

   greatest f seq returns the item in seq that maximizes function f. For example:

   > greatest sum [[2,5], [-1,3,4], [2]]
   [2,5]
   
   > greatest length ["the", "quick", "brown", "fox"]
   "quick"
   
   > greatest id [51,32,3]
   51
   

   If more than one item maximizes f, then greatest f returns the first one.

Basic Bits

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

   Include the most general type signature.

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

   Include the most general type signature.

9. In the following questions, x is a list of Int values, and the returned value has type Bool. Include the most general type signature for each function.

   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). It should return False otherwise.

      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 don’t use recursion, guarded commands, or if- then-else in your solution. Instead, use a higher-order function to calculate the answer in one expression.

10. In each of the following functions, x is a list of Int values, and the type of the returned value is also a list of Int. Include the most general type signature for each function.

    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 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 implement it using a list comprehension (and no recursion, and no map function).

11. (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), meaning there is one 0 and three 1s in the list.

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

    Include the most general type signature.

12. (1 mark) Write a function called all_basic_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.

    Include the most general type signature.

A Custom List Data Type

Haskell has good built-in support for lists that you should use for most programs. However, it’s instructive to implement our own list type. We’ll do it as follows:

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

This is an algebraic data type. It defines a new type called List a, that represents a list of 0, or more, values of type a. A List a is either Empty, or it is of the form (Cons first rest), where first is a value of type a, and rest is a value of type List a. This mimics the common “cons cell” implementation of lists in Lisp.

The line deriving Show is added as a convenience: it lets Haskell convert a List a to a string for printing.

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

14. (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 questions, do not use toList or toHaskellList in your implementations. Only use them for testing and debugging. Stick to basic recursion and Haskell prelude functions for your solution code.

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

15. (1 mark) Implement append A B, 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))))
    

16. (1 mark) Implement the function removeAll f L 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. f is a predicate function of type a -> Bool and L has type List a.

    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)
    

17. (1 mark) Implement sort L, where L has type List a, that returns a new List a that is a sorted version of 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)))