PA-H02: Haskell Programming Assignment 2

Note

These notes are applicable to all Haskell assignments. Please read carefully before you start the assignment, they are important.

  • You must name your functions exactly as written on this page. This includes spelling and case of the function name. The functions are automatically graded, and the autograder script will not be able to find your function if you do not name it correctly.
  • You may be required to use a certain Haskell feature to solve a problem. If the question asks for this, you must use that feature in a non-trivial manner to receive full points for the problem. For example, I make ask you to use a list comprehension. If the assignment asks for it to be implemented that way, you must implement it that way.
  • Unless otherwise asked, your functions must handle the case where you are passed an empty list (or other structure) correctly. For example, if asked to find the number of odd elements in an empty list, the correct answer should be 0 (not an error).
  • In functions that return a string or produce output, you must match the output formatting correctly, byte-for-byte (unless otherwise noted).
  • You should test more cases than listed on this page. The autograder has a large number of test cases, not all of which you see here. I am unable to give students all of the test cases that the autograder uses as then you could (in theory) just hard-code the answers. If you are having issues on a specific test case, come in during office hours and we can look at it.
  • You only get 4 submissions on the autograder before you will have to Email me and ask for more. Use them wisely, and test your code before uploading.

Note

Writing type declarations is optional, but highly recommended!

  1. (3 points) Write a function named getUserName that takes an Email address and returns the first part (everything before the @):

    GHCi> getUserName "jrosenth@mines.edu"
    "jrosenth"
    GHCi> getUserName "jack@rosenth.al"
    "jack"
    

    If you don’t know where to start, I might recommend using recursion. But feel free to be creative and solve this problem whichever way you choose.

  2. (1 point) Write a function called count which takes a list (with data of any type) and returns the number of items in the list:

    GHCi> count [1,2,3,4,5]
    5
    GHCi> count ["hello","world"]
    2
    GHCi> count [[1,2],[3,4],[0,0]]
    3
    GHCi> count []
    0
    

    Note

    Your solution must make good use of recursion. You cannot use Haskell’s builtin length function anywhere in your solution.

  3. (2 points) Write a function called recursiveRange which takes two integers and returns a list with all the integers from the first up to and including the second:

    GHCi> recursiveRange 1 5
    [1,2,3,4,5]
    GHCi> recursiveRange 5 5
    [5]
    GHCi> recursiveRange (-1) 1
    [-1,0,1]
    

    When the first integer is larger than the second, you should return the empty list:

    GHCi> recursiveRange 6 5
    []
    

    Hint

    Guards, anyone?

    Note

    Your solution must make good use of recursion.

  4. (2 points) Write a separate function called recursiveReverseRange which takes two integers and returns a list with all the integers from the first down to and including the second:

    GHCi> recursiveReverseRange 5 1
    [5,4,3,2,1]
    GHCi> recursiveReverseRange 5 5
    [5]
    

    When the first integer is smaller than the second, you should return the empty list:

    GHCi> recursiveReverseRange 4 5
    []
    

    Note

    Your solution must make good use of recursion. You should not use your recursiveRange function in your solution.

  5. (4 points) Write a function called subList which takes two integers (more specifically, of Int type rather than the Integral type class) and a list. The function should return the part of the list from the index of the first integer, and the second integer indicates the number of elements to extract:

    GHCi> subList 2 3 [1..]
    [3,4,5]
    GHCi> subList 0 1 [1..]
    [1]
    GHCi> subList 1 0 [1..]
    []
    GHCi> subList 3 5 "CS@Mines"
    "Mines"
    

    Note

    Your solution must make good use of recursion.

  6. (4 points) Write a function called merge which takes two already sorted lists and merges them together to create one sorted list:

    GHCi> merge [1,3,5,9] [0,2,10]
    [0,1,2,3,5,9,10]
    GHCi> merge [] [1,2,3]
    [1,2,3]
    GHCi> merge [1,2,3] []
    [1,2,3]
    GHCi> merge [] []
    []
    

    Note

    Your solution must make good use of recursion. Further, your function should not make use of any sorting functions (such as Haskell’s builtin sort function).

  7. (4 points) Use your merge function to write a function called mergeSort that implements the MergeSort algorithm. Essentially:

    1. If the length of the input list is zero or one, the list is already sorted. Return the list as it is.
    2. Otherwise, take the input list and split it in half (your choice on which list is bigger when there is an odd number of elements). Call mergeSort on the left side and the right side, then call merge on the two sorted lists.
    GHCi> mergeSort [3,6,1,4,9,5,2]
    [1,2,3,4,5,6,9]
    GHCi> mergeSort [2,1]
    [1,2]
    GHCi> mergeSort [1]
    [1]
    GHCi> mergeSort []
    []
    

    Note

    Certain things like let, where, as-patterns, etc. may make solving this problem much easier. Using them is not required, but I highly recommend you use these tools where you can.

  8. (2 points) Create a function multRange which takes the same arguments as recursiveRange, but returns a list of partially applied multiplication functions for each number in the range. For example, multRange 1 5 should be [(1*),(2*),(3*),(4*),(5*)].

    Note

    GHCi will not be able to print the result of your function. If you try and do this, you’ll get a scary looking error:

    • No instance for (Show (Integer -> Integer))
        arising from a use of ‘print’
        (maybe you haven't applied a function to enough arguments?)
    • In a stmt of an interactive GHCi command: print it
    

    This is because we still have partially applied functions in our result.

    A good way to test your function would be to look at a specific index, and then call it to see if it gives the right result. Spot check your function for a few different results. This is how the autograder will grade your function:

    GHCi> ((multRange 1 5) !! 3) 5
    20
    GHCi> (head $ multRange 10 20) 10
    100
    

    Also, using recursion is optional on this problem, and feel free to use your recursiveRange if it helps. I used map for my solution.

  9. (3 points) Use your multRange function to generate a row of a 10x10 multiplication table. Call this function multTableRow:

    GHCi> multTableRow 3
    [3,6,9,12,15,18,21,24,27,30]
    GHCi> multTableRow 5
    [5,10,15,20,25,30,35,40,45,50]
    

    Hint

    Use $ to apply the number you are given to each function your multRange gives you.

    Note

    You must use your multRange function in your solution.

Submit

Before submitting, read the important notes at the top of this assignment.

This assignment is due Wednesday, Feb 21 at 11:59 PM.

Do not write a module ... where line for this assignment (kudos if you know what it is though!)

Do not write a main function.

Submit your .hs file on Gradescope.