联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2019-10-16 10:32

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

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.


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp