Skip to content

README

Jump to bottom
Lindsey Kuper edited this page May 9, 2024 · 32 revisions

Assignment 1: Haskell Crash Course (97 points)

The objective of this assignment is for you to gain some hands-on experience with Haskell.

At first glance, you might wonder, "What does this homework assignment have to do with learning the foundations of programming languages?" Great question! There are a few reasons:

  • Much of the field of PL is about programs that operate on programs. Interpreters, compilers, program analyzers, emulators, fuzzers, debuggers, and so on, are all programs that operate on programs. There are many things about Haskell that make it well suited for expressing programs that operate on programs, and so it is the main tool we'll be using in this course. It's therefore worth the time to invest some effort up front in getting comfortable with using it. You can do PL without using Haskell, but Haskell is a nice language to have in your toolbox if you want to do PL.

  • Haskell itself is an example of sophisticated programming language design, so using it will expose you to some interesting PL design ideas that have influenced many other languages. (But you don't have to take our word for it! For example, check out what Matt Might has to say about reasons to learn Haskell.)

All the problems on this assignment require relatively little code ranging from 2 to 15 lines. If any function requires more than that, you can be sure that you need to rethink your solution.

Start Early! Haskell, while simple, may seem foreign at first, particularly when it comes to recursion and list manipulation.

Environment and Setup

To complete this assignment, you will need the following tools installed. You can either install these on your own system, or use the CSE 114A Dev Container, which has everything you need preinstalled.

  • Haskell's Stack toolchain
    • The Stack website has specific instructions for each operating system (e.g. Windows, MacOS).
  • The UCSC autograder command-line interface
    • This can be installed using python3 -m pip install autograder-py.
    • You will need to have Python installed on your system to use the autograder client.

Next, you need to configure the autograder client (so that it knows who you are!). This config file contains your credentials, so config.json should not be committed to your Git repository. (This is especially important for group assignments!)

  1. Copy the provided config.example.json file into a new config.json file.
    • WARNING: Do not use a config file from any other source! If you use a different assignment's config, you may inadvertently submit to the wrong assignment, potentially losing points across both assignments.
  2. Replace the "user" field in config.json with your UCSC student emial.
  3. Replace the "pass" field in config.json with the special autograder password you should have received at the start of the course.
    • WARNING: This is not the same as your UCSC Blue or Gold password -- that's the wrong password!
    • If you haven't received an email with an autograder password, contact course staff.

You can use the command python3 -m autograder.cli.submission.peek to check whether your configuration is correct. If you haven't submitted to this assignment yet, you should see the following output:

No past submission found for this assignment.

If you see something else, you may be submitting to the wrong assignment -- double-check the steps above to make sure you haven't copied a configuration from the wrong location!

Submission Instructions

When you are ready to submit your solutions to the autograder, follow these instructions step-by-step:

  1. You must create a file INTEGRITY.md at the top level of your assignment repository in which you give credit to all sources you used while working on the assignment. Thorough citation is the way to avoid running afoul of accusations of misconduct.
    • So that you have an idea of the level of detail that is expected, there is an example INTEGRITY.md file that you can reference.
    • If you didn't reference any external sources, just say so in INTEGRITY.md.
  2. Commit your changes and push your Git repository. (You should be doing this regularly anyway!)
  3. Submit your solutions using the autograder client: 
    python3 -m autograder.cli.submission.submit INTEGRITY.md src/Hw1.hs
    This command will submit your code for evaluation and print out the autograding results.

You can submit as many times as you like before the deadline, and only the last submission will be counted.

The autograder client has several other commands that you might find useful.

  • To see the results of your last submission, use python3 -m autograder.cli.submission.peek.
  • To see the results of all of your previous submissions, use python3 -m autograder.cli.submission.history.

The autograder client documentation has a fuller list of commands and their uses.

If you cannot get your implementation of a function to compile by the time you submit your solutions, leave the broken function defined as error ..., with your partial solution enclosed below as a comment. Since all of your solutions are compiled together, a compile-time error with one solution would prevent all of them from being graded!

Solving the Problems

In this assignment, you will edit the src/Hw1.hs file. This file contains a set of functions with bodies that simply throw an error (error "TBD: "); your mission is to complete those functions according to the problem descriptions below. You should only need to modify the parts of the files that say error "TBD: ..." with suitable Haskell implementations. However, you may define your own helper functions if it helps you; and if you're asked to fill in a function definition, such as:

f xs = error "TBD: ..."

you are also allowed to split this definition into multiple equations, like so:

f []     = ...
f (x:xs) = ...

You are allowed to use any library function on integers, but only the following library functions when dealing with lists:

  • length :: [a] -> Int, to compute the number of elements in a list;
  • (++) :: [a] -> [a] -> [a], to combine two lists sequentially into one; and
  • (==) :: [a] -> [a] -> Bool, to check whether two lists are identical.

You may also use the list constructors [] and (:); in fact, you won't be able to complete the assignment without using them.

Banned functions include (but are not limited to) sum, read, show, reverse, map, and filter. If you are not sure whether a function is allowed, ask an instructor!

Checking your Solutions

As you complete each problem, you should run stack test to check for various possible issues with your solution. If any tests fail, you will not get full credit. Conversely, you should assume that the autograder may run some additional tests that are not included with the assignment; so having a clean stack test does not necessarily mean that your assignment will get full points. You should only trust the numbers reported by the autograder when you submit your assignment.

When you run stack test, the end of the output should include the lines

All N tests passed (...)
OVERALL SCORE = ... / ...

or

K out of N tests failed
OVERALL SCORE = ... / ...

If your output does not have one of the above, your code will receive a zero.

The other lines will give you a readout for each test. You are encouraged to try to understand the testing code, but you will not be graded on this.

You may also find it useful to use the Haskell interpreter, GHCi, to test your code by hand. To do this, run the stack ghci command, which should wait for further input on a ghci> prompt. You can enter Haskell expressions at this prompt to evaluate them, including expressions that use functions defined in the assignment. The ghci documentation has a fuller introduction to GHCi.

Problem Descriptions

Part 1: Palindromes (35 points)

In this part, you will implement a function palindrome :: String -> Bool that determines whether a given string is a palindrome -- that is, whether it is spelled the same backwards and forwards, like "racecar" and "step on no pets". We'll do this by implementing two separate functions that are easier to implement.

Problem 1(a): Reversing a list (20 points)

Implement a function listReverse :: [a] -> [a] that takes a list of elements and returns a list with those same elements in the exact opposite order.

This function should have the following example behavior:

ghci> listReverse [1, 2, 3, 4]
[4, 3, 2, 1]

ghci> listReverse ["i", "want", "to", "ride", "my", "bicycle"]
["bicycle", "my", "ride", "to", "want", "i"]

Problem 1(b): Recognizing palindromes (15 points)

Implement a function palindrome :: String -> Bool that takes a string and returns True if that string is a palindrome, and False otherwise. You can (and should) use listReverse as part of your implementation; if you find yourself writing more than one short line of code, you should reconsider your approach. In particular, note that the String type is defined as [Char], i.e. a string is just a list of characters.

This function should have the following example behavior:

ghci> palindrome "malayalam"
True

ghci> palindrome "palindrome"
False

Part 2: Credit card number validation (62 points)

In this part, you will implement a function validateCardNumber :: Integer -> Bool that determines whether a given credit card number is valid. Credit card number validation follows a sequence of steps (known as the Luhn algorithm), so we'll break the process down into a collection of simpler functions that are easier to implement.

Suppose our credit card number is 4012 0000 7777 7777 (which is one of the specially-allocated test numbers used by PayPal). To validate this number, we must follow this procedure:

  • Double every second digit starting from the right-hand side; if a digit like 6 doubles to 12, treat the result as two separate digits. For our test number, this yields 8022 0000 147147 147147.
  • Add up all of the digits. For our test number, this yields 60.
  • Determine if this sum is divisible by ten; if it is, the card number is valid. Our test number is valid, because 60 is indeed divisible by 10.

(This part of the assignment was adapted from Brent Yorgey's course materials.)

Problem 2(a): Turning an integer into a list of digits (12 points)

Implement a function digitsOfInt :: Integer -> [Integer] that takes a positive integer and returns a list of its digits, with its most significant digit first. If the integer is negative or zero, an empty list should be returned instead.

This function should have the following example behavior:

ghci> digitsOfInt 3124
[3, 1, 2, 4]

ghci> digitsOfInt 352663
[3, 5, 2, 6, 6, 3]

Problem 2(b): Turning a list of integers into a list of digits (5 points)

Implement a function digitsOfInts :: [Integer] -> [Integer] that takes a list of integers and returns a list of its digits in the same order they appear in the given list. You will want to use digitsOfInt to implement this function.

This function should have the following example behavior:

ghci> digitsOfInts [3124, 52, -42, 8]
[3, 1, 2, 4, 5, 2, 8]

Problem 2(c): Doubling with skips (15 points)

Implement a function doubleEveryOther :: [Integer] -> [Integer] that takes a list of integers and returns the same list of integers, but with every second element doubled.

This function should have the following example behavior:

ghci> doubleEveryOther [8,7,6,5]
[8,14,6,10]

ghci> doubleEveryOther [1,2,3]
[1,4,3]

Problem 2(d): Summing over a list (10 points)

Implement a function sumList :: [Integer] -> Integer that takes a list of integers and adds them up to produce a single sum.

This function should have the following example behavior:

ghci> sumList [1, 2, 3, 4]
10

ghci> sumList [1, -2, 3, 5]
7

ghci> sumList [1, 3, 5, 7, 9, 11]
36

Problem 2(e): Card validation (20 points)

Implement a function validateCardNumber :: Integer -> Bool that takes a credit card number (represented as a single, very large integer) and returns True if it is valid according to the validation procedure described above, and False otherwise. This function can (and should) use every other function defined in this assignment, except palindrome. (If a credit card happens to also be a palindrome, this makes the owner of the card very happy, but digital merchants don't particularly care.)

This function should have the following example behavior:

ghci> validateCardNumber 4012888888881881
True

ghci> validateCardNumber 4012888888881882
False
Clone this wiki locally