159.202-2019 Semester 2 Massey University
1
Assignment 5
Deadline: Hand in by 5:00 p.m. on Friday 18th of October
Evaluation: 10 marks – which is 3% of your final grade
Late Submission: 1 mark off per day late
Work: This assignment must be done individually.
Purpose: Haskell Higher Order Functions
Run-Length Encoding (RLE) is a simple, lossless compression algorithm that detects sequential, identical data
elements and replaces them with a single data element and a number representing the number of times that
element should appear. For example, the following String (list of characters):
AAAAABBBEEECEDDDDDDDAAAA
Could be encoded using RLE as
A5B3E3C1E1D7A4
In some cases (e.g. when every sequential element is different) then RLE may not compress the data but actually require
代做159.20留学生作业
even more memory. However, this type of encoding can be very useful for images that often contain large regions of the
same colour.
a) Write an RLE encoding function:
Write a Haskell function named encodeA that encodes a list using Run-Length Encoding and produces a list
of tuples (consisting of the element and the count). Some expected output is shown below.
Main> encodeA [1,1,1,1,3,4,4,4,4,4,5,5,1,1,22,2,2,2]
[(1,4),(3,1),(4,5),(5,2),(1,2),(22,1),(2,3)]
Main> encodeA "AAAAABBBEEECEDDDDDDDAAAA"
[(‘A‘,5),(‘B‘,3),(‘E‘,3),(‘C‘,1),(‘E‘,1),(‘D‘,7),(‘A‘,4)]
b) Write an RLE decoding function:
Write a Haskell function named decodeA that decodes a list of tuple (as generated by encodeA) using RunLength
Encoding and produces the unencoded list of elements.
Main> decodeA [(‘a‘,3),(‘b‘,4),(‘c‘,1),(‘e‘,2)]
"aaabbbbcee"
c) Write an RLE encoding function using Higher-Order functions:
For this question you will need to three functions, the first packtuple should take a single element and pack
it into a tuple where the second element is an integer with value 1.
The second function combine should take a tuple (element,count) and list of tuples
[(element,count)]. If the tuple has the same element as the first tuple in the list, then the count of the
first tuple in the list should be set to the sum of the two count values. If two elements are different, the tuple
should simply be added to the head of the list.
Finally, you should write a Haskell function named encodeB that uses your two functions packtuple and
combine together with the built-in higher-order functions map and foldr to encode a list using Run-Length
Encoding.
Some expected output is shown below (the output of encodeB should be the same as encodeA).
159.202-2019 Semester 2 Massey University
2
Main> packtuple ‘A‘
(‘A‘,1)
Main> combine (‘A‘,1) [(‘A‘,4),(‘D‘,4),(‘C‘,2)]
[(‘A‘,5),(‘D‘,4),(‘C‘,2)]
Main> combine (‘B‘,1) [(‘A‘,4),(‘D‘,4),(‘C‘,2)]
[(‘B‘,1),(‘A‘,4),(‘D‘,4),(‘C‘,2)]
d) Write image encoding/decoding functions that use RLE to compress/decompress a Word8 list.
The Haskell Word8 type can store an 8-bit integer. Write functions to encode and decode a list of Word8
elements using RLE. Important: this encoding function should behave differently to those from part a and b.
Instead of producing a list of tuples [(Word8,Int)] it should produce a Word8 list where alternating
elements represent an element and then a count respectively. The decode function should reverse this process
and produce the decoded list. Expected behaviour is shown below:
Main> encode [1,1,1,1,1,4,4,4,2,2,2,2]
[1,5,4,3,2,4]
Main> decode [1,3,2,5,8,2,9,1]
[1,1,1,2,2,2,2,2,8,8,9]
If there are more than 255 identical elements in a row then the count would overflow an 8-bit integer. This
should be split into multiple entries. For example, the encoded form of a list consisting of 600 2s in a row
would be [2,90,2,255,2,255]
e) Write image compression/decompression functions that use RLE to compress/decompress an image.
Haskell can read and write binary data files. The sample code provided on the stream site provides an example
function that can open a binary image file (.bmp), read its contents into a list of Word8 and then write a copy
of it to file. An example of using this function is shown below:
Main> copyImage "test.bmp" "copy.bmp"
Create two modified versions of this. The first should open a (.bmp) file, encode the image using your RLE
encoding function from part d and write it to an output file (a .rle file). The second should open an encoded
file, decode it using your decoding function from part d and write it to an output image file (.bmp) which
should be exactly the same as the original image. Compare the size of the encoded and unencoded files. Note:
do not expect to be able to open the .rle file with an image viewer.
f) Bonus marks - Write an RLE encoding function using a lambda function and function composition:
Write another RLE encoding function named encodeC that uses the function composition operator and a
lambda function. You should use your combine function, the higher-order functions map and foldr.
You must put the following comments at the top of your program code and provide the appropriate information.
-- Assignment number, 159.202, 2019 S2
-- Family Name, Given Name, Student ID,
-- Explain what the program is doing . . .
Hand-in: Submit your script electronically through stream
If you have any questions about this assignment, please ask the lecturer.
因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：[email protected]
微信：codehelp