Assignment

Written Part

Write a math definition for Euclid's algorithm for calculating the greatest common divisor of two non-negative integers, and use equational reasoning (aka calculation, as shown in class and in the textbook (pp. 3-4, 5-6, 9, 11, 59-60, 61, 62, 63, 64, 65, 66, 75, 79, 83-84, . . . ) to show that

euclid 6 27 == 3

If you do not know/recall Euclid's algorithm, it is:
- if the two numbers are equal, then that number is the result
- otherwise the smaller number is subtracted from the larger, and we recurse with the result of the subtraction and the smaller number.

Programming Part

P2

Practice the five-step process given in the textbook, complete questions 7 and 8 from chapter 6. To wit,

§6.7Define a recursive function

merge :: Ord a ⇒ [a] → [a] → [a]

that merges two sorted lists to give a single sorted list. For example:

> merge [2,5,6] [1,3,4]
[1,2,3,4,5,6]

You do not need to show the five steps, but it might help you build the functions.

Note: your definition should not use other functions on sorted lists, such as insert or isort, but should be defined using explicit recursion.

§6.8Using your merge function, define a function

msort :: Ord a ⇒ [a] → [a]

that implements merge sort, in which an empty list and singleton lists are already sorted, and any other list is sorted by merging together two lists that result from sorting the two halves of the list separately.

Hint: first define a function

halve :: [a] → ([a], [a])

that splits a list into two halves whose lengths differ by at most one. Submit one file, abc123-a2q2.hs (where abc123 is replaced with your NSID) containing your solution and some test cases, including data other than just integers.

P3 Complete questions 7 and (an extended version of) 8 from chapter 7. To wit, extend the binary string-transmitter example on pp. 82-85 in the textbook,

import Data.Char type Bit = Int
bin2int :: [Bit] → Int
bin2int = foldr (λx y → x + 2×y) 0
unfold :: (a → Bool) → (a → b) → (a → a) → a → [b] unfold p h t x | p x = []
| otherwise = h x : unfold p h t (t x)
int2bin :: Int → [Bit]
int2bin = unfold (==0) (‘mod‘ 2) (‘div‘ 2)

make8 :: [Bit] → [Bit]
make8 bits = take 8 (bits ++ repeat 0)

encode :: String → [Bit]
encode = concat ? map (make8 ? int2bin ? ord)
chop8 :: [Bit] → [[Bit]]
chop8 = unfold null (take 8) (drop 8)

decode :: [Bit] → String
decode = map (chr ? bin2int) ? chop8
transmit :: String → String transmit = decode ? channel ? encode
channel :: [Bit] → [Bit] channel = id

test :: String → Bool test s = (s == transmit s)

s1 = "higher-order.functions.are.easy"
s2 = "learn.you.a.Haskell.for.great.good"

-- enter these at GHCi to run tests
-- test s1
-- test s2

by answering the following questions:

§7.7 Modify the binary-string transmitter example to detect simple transmis- sion errors using the concept of parity bits. That is, each eight-bit binary number produced during encoding is extended with a parity bit at the end, set to one if the number contains an odd number of ones, and to zero otherwise. In turn, each resulting nine-bit binary number consumed during decoding is checked to ensure that its parity bit is correct, with the parity bit being discarded if this is the case, and a parity error being reported otherwise.
Hint: the library function

error :: String → a

displays the given String as an error message and terminates the program; the polymorphic result type ensures error can be used in any context.

§7.8 Test your new string transmitter program from the previous exercise using three faulty communication channels:

a) a faulty communication channel that zeroes the second bit of every nine-bit binary number

b) a faulty communication channel that swaps the first and second bits of every nine-bit binary number

c) a faulty communication channel that forgets the first bit of every nine- bit binary number, which can be modelled using the tail function on lists of Bits

Submit three files,
abc123-a2q3a.hs, abc123-a2q3b.hs, and abc123-a2q3c.hs

(where abc123 is replaced with your NSID) containing your solutions to the corresponding parts along with test cases. Note that the first two faulty com- munications channels are occasionally correct-include examples that can be transmitted correctly and examples that cannnot be transmitted correctly.