3.13 Generalized Sorting

Answers to Exercises

Problem 1

• Suppose L is a list of lists. Present an expression which will return the lists of elements in L having length greater than 5.

rex> keep((X) => length (X) > 5, L);

Problem 2

••• Present as many functional identities as you can among the functions keep, find_indices, map, append, and reverse, excluding those presented in earlier exercises.

Problem 3

••• Show how we could use keep and map in combination to define a function gather which creates a list of second elements corresponding to a given first element in an association list. For example,

rex > gather(3, [[1, "a"], [2, "b"], [3, "c"], [1,"d"], [3, "e"], [3, "f"], [2, "g"],[1, "h"]]);
[c, e, f]

There are different ways to do this. Here, we begin with a 'keep' function which generates a list of all the pairs that begin with the first input value. Then, using map to apply the 'second' function to the elements of our created list, we create a new list of all of the second cartesian coordinate values from the first list.

rex> gather(A,L) = map((X) => second(X), keep((Y) => first(Y) == A,L));

Problem 4

••• Then define a second version of gather which gathers the second components of all elements of an association list together:

rex > gather([[1, "a"], [2, "b"], [3, "c"], [1,"d"],[3, "e"], [3, "f"], [2, "g"], [1, "h"]]);
[[1, a, d, h], [2, b, g], [3, c, e, f]]

In this solution assume there is already a function 'gather' assigned as found in the solution to Problem 3. Here we will apply the already defined 'gather' statement for two arguments using the first value of each set of pairs and the list L as its arguments. We do this by using two functions of 'map' to find the 'first' value, then to apply that value to the two-ary 'gather'. At the same time, we want to place the 'first' value at the head of the list, so we modify the contents of the 'map' function containing the two-ary 'gather' function to place the 'first' value at it's head. The result is a list of lists of the two-ary 'gather' function applied to the first value of each of the pairs in list L. We have to remove the duplicates of this list using 'remove_duplicates.'

rex> gather(L)=remove_duplicates(map((X) => [X | gather (X, L)], map((Y) => first(Y), L)));