Module Code: CMT304
Module Title: Programming Paradigms
Assessment Title: Functional Programming
Assignment
Consider a small binary image (or 2D array or matrix) that is represented as a list of lists which contains only the numbers 0 or 1, e.g.,
[[0,0,0,0,1,1],
[1,1,1,1,1,0],
[1,1,0,0,1,0],
[1,1,0,0,1,1],
[1,0,1,1,1,1]]
We wish to find the number of pixels in the largest connected component of such images (there can of course be more than one component with the same largest number). A connected component is a cluster of pixels that contain the same value and there is a path from each pixel to each other pixel inside that cluster. A pathis formed from a start pixel by moving either horizontally (one element left or right in the same inner list) or vertically (one list up or down in the outer list without changing the position in the inner list) to the next pixel until the end pixel is reached (this is 4-pixel connected,i.e. no diagonal movement). The number of elements in the largest connected component for the value 0 in the above example is 4 (among the 4 components). It is 19 for the value 1 (there is only one component).
Task 1: Write an efficient Haskell function
nlcc l v
that finds the number of elements in the largest connected component of the binary image (list of lists) l for the value v. Note, there are multiple, more or less efficient algorithms to solve this problem – make sure you clearly document your approach. Also note, you must write a function, not a full program (so no main, etc.) and it must have the above name with two arguments (failing to do so may result in 0 marks for this task). Make sure your Haskell code can be compiled/interpreted without errors (otherwise 0 marks may be assigned for this task).
Note that you must write your own code to solve this problem and not just call a library function, or copy code from some other source (independent of plagiarism issues, even if you reference; you only get marks for your own work). You may use the standard libraries listed in the Haskell 2010 language report, but not any other libraries (otherwise the code will be treated as not compilable/interpretable, which may result in 0 marks for this task).
Task 2: Write a report of up to 500 words (this is an upper limit, not a target) as described below:
(a) Discuss one feature of the functional programming paradigm that is useful to solve this problem and compare it to another paradigm of your choice that does not have this feature.
(b) Discuss one feature of the functional programming paradigm that makes it difficult to solve this problem and compare it to another paradigm of your choice that would make it simpler.
Clearly indicate which of the two points above you address. Make sure you discuss only one feature per point above; only the first feature you discuss for each point will be considered.
Learning Outcomes Assessed
• Explain the conceptual foundations, evaluate and apply various programming paradigms, such as logic, functional, scripting, filter-based programming, pattern matching and quantum computing, to solve practical problems.
• Discuss and contrast the issues, features, design and concepts of a range of programming paradigms and languages to be able to select a suitable programming paradigm to solve a problem.