HW 0, due 9/30/2016

Download

Overview

This is a warm up assignment which will

  • refresh your memory of functional programming from CSE 130, and
  • provide a quick introduction to Haskell.

To this end, you will, reimplement certain problems from CSE 130 in Haskell. Recall that the problems 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.

  1. lib/Hw0.hs has skeleton functions with missing bodies that you will fill in,
  2. tests/Test.hs has some sample tests, and testing code that you will use to check your assignments before submitting.

You should only need to modify the parts of the files which say:

with suitable Haskell implementations.

Note: Start early, to avoid any unexpected shocks late in the day.

Assignment Testing and Evaluation

Your functions/programs must compile and run on ieng6.ucsd.edu.

Most of the points, will be awarded automatically, by evaluating your functions against a given test suite.

Tests.hs contains a very small suite of tests which gives you a flavor of of these tests. When you run

$ stack test

Your last lines should have

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

If for some problem, you cannot get the code to compile, leave it as is with the error ... with your partial solution enclosed below as a comment.

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.

Submission Instructions

To submit your code, just do:

turnin will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin matches the size of your file. See the ACS Web page on turnin for more information on the operation of the program.

Problem 1: Roots and Persistence

(a) 10 points

Fill in the implementation of

that such that sumList xs returns the sum of the integer elements of xs. Once you have implemented the function, you should get the following behavior at the prompt:

(b) 10 points

Fill in the implementation of the function

such that digitsOfInt n

  • returns [] if n is not positive, and otherwise
  • returns the list of digits of n in the order in which they appear in n.

Once you have implemented the function, you should get the following:

(c) 10+10 points

Consider the process of taking a number, adding its digits, then adding the digits of the number derived from it, etc., until the remaining number has only one digit. The number of additions required to obtain a single digit from a number n is called the additive persistence of n, and the digit obtained is called the digital root of n.

For example, the sequence obtained from the starting number 9876 is 9876, 30, 3, so 9876 has an additive persistence of 2 and a digital root of 3.

Write two functions

that take positive integer arguments n and return respectively the additive persistence and the digital root of n. Once you have implemented the functions, you should get the following behavior at the prompt:

Problem 2: Palindromes

(a) 15 points

Without using any built-in functions (e.g. reverse), write an function:

such that listReverse [x1,x2,...,xn] returns the list [xn,...,x2,x1] i.e. the input list but with the values in reversed order. You should get the following behavior:

###(b) 10 points

A palindrome is a word that reads the same from left-to-right and right-to-left. Write a function

such that palindrome w returns True if the string is a palindrome and False otherwise. You should get the following behavior:

Problem 3: Folding Warm-Up

(a) 15 points

Fill in the skeleton given for sqsum, which uses foldl' (the equivalent of Ocaml’s List.fold_left) to get a function

such that sqSum [x1,...,xn] returns the integer x1^2 + ... + xn^2

Your task is to fill in the appropriate values for

  1. the folding function f and
  2. the base case base.

Once you have implemented the function, you should get the following behavior:

(b) 30 points

Fill in the skeleton given for pipe which uses foldl' to get a function

such that pipe [f1,...,fn] x (where f1,...,fn are functions!) should return f1(f2(...(fn x))).

Again, your task is to fill in the appropriate values for

  1. the folding function f and
  2. the base case base.

Once you have implemented the function, you should get the following behavior:

(c) 20 points

Fill in the skeleton given for sepConcat, which uses foldl' to get a function

Intuitively, the call sepConcat sep [s1,...,sn] where

  • sep is a string to be used as a separator, and
  • [s1,...,sn] is a list of strings

should behave as follows:

  • sepConcat sep [] should return the empty string "",
  • sepConcat sep [s] should return just the string s,
  • otherwise (if there is more than one string) the output should be the string s1 ++ sep ++ s2 ++ ... ++ sep ++ sn.

You should only modify the parts of the skeleton consisting of error "TBD" ". You will need to define the function f, and give values for base and l.

Once done, you should get the following behavior:

(d) 10 points

Implement the function

such that stringOfList f [x1,...,xn] should return the string "[" ++ (f x1) ++ ", " ++ ... ++ (f xn) ++ "]"

This function can be implemented on one line, without using any recursion by calling map and sepConcat with appropriate inputs.

You should get the following behavior:

Problem 4: Big Numbers

The Haskell type Int only contains values up to a certain size (for reasons that will become clear as we implement our own compiler). For example,

You will now implement functions to manipulate arbitrarily large numbers represented as [Int], i.e. lists of Int.

(a) 10 + 5 + 10 points

Write a function

such that clone x n returns a list of n copies of the value x. If the integer n is 0 or negative, then clone should return the empty list. You should get the following behavior:

Use clone to write a function

which takes two lists: [x1,...,xn] [y1,...,ym] and adds zeros in front of the shorter list to make the lists equal.

Your implementation should *not** be recursive.

You should get the following behavior:

Next, write a function

that takes a list and removes a prefix of leading zeros, yielding the following behavior:

(b) 25 points

Let us use the list [d1, d2, ..., dn], where each di is between 0 and 9, to represent the (positive) big-integer d1d2...dn.

For example, [9, 9, 9, 9, 9, 9, 9, 9, 9, 8] represents the big-integer 9999999998. Fill out the implementation for

so that it takes two integer lists, where each integer is between 0 and 9 and returns the list corresponding to the addition of the two big-integers. Again, you have to fill in the implementation to supply the appropriate values to f, base, args. You should get the following behavior:

(c) 15 + 20 points

Next you will write functions to multiply two big integers. First write a function

which takes an integer digit and a big integer, and returns the big integer list which is the result of multiplying the big integer with the digit. You should get the following behavior:

Now, using mulByDigit, fill in the implementation of

Again, you have to fill in implementations for f , base , args only. Once you are done, you should get the following behavior at the prompt: