Assignment 3, Task 2 and Task 4

[tmuecksch]

Hey there,

I got some questions:

Question regarding task 2:
In the task description we are asked to implement a function which computes a sublist.

Implement the function sublists which takes a list xs and computes the set X of all lists such that for all ys in X, ys is the result of removing some (or no) elements from xs. Implement sublists with some flavor of fold.

I don't exactly get how these sublists are supposed to be assembled. The description doesn't answer some questions. It says "[...] ys is the result of remove some (or no) elements from xs." This doesn't specify if all permutations have to be in the list, or just one we can randomly pick.

Question regarding task 4:
In the fourth task we have to implement a fold function on a binary tree. It is not specified how a fold function would work on binary trees and I was not able to find any hints on the internet. Could you please specify this function or refer to an adequate source?

Thanks in advance!

[Talaron]

Not official, but as the tests are passed I guess I got the tasks right:

Task 2: What we are supposed to implement is comparable to the power set of a mathematical set, except that the original order of the remaining elements has to be retained.

An example would be: sublists((1,2,3)) = {(), (1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)}


Task 4: Here it helped me a lot to look at the function's signature: "fold[T,R](tree: Tree[T])(init: R)(f : (T, R, R) => R): R"

The function given as parameter takes a tree node and two already computed results to create a new result. I can see only one logical way/direction to apply such a function in a binary tree that ends in a single result created from the tree.

[Dennis Albrecht]

Task 2:
The description is rather complex but the task is simply to return a set of all possible sublists.

Task 4:
Folding lists and trees is rather similar:
A list is either the empty list or a concatenation of an element/value and another list (itself either being [...]).
A binary tree is either the empty tree or a combination of an element/value and two other trees (themselves being either [...]).

Folding a list means to "somehow" combine a value with the result of the sublist.
Therefore, folding a tree means to "somehow" combine a value with ... (the rest is let open for your own creativity, little hint: the words "result" and "sub-" will be needed).

Greets Dennis