Filtering directly and indirectly connected things from list

Question

Hello,

if you have a function "test a b" which returns true if a and b are connected directly and if you have a given unordered list of things, what would be an elegant and fast solution to filter all connected things from given list?

Example:

let test a b = let diff = a - b in diff == 0 ;;

let lst = [4;1;7;3;8;9;2;0] ;;

filter_connected 2 lst ;;

-> [4;1;3;2;0]

Any hints?

Answer 1

I will assume that you want to get the elements of the original list that are at distance less than 2 from 2.

        Objective Caml version 3.11.1

# let test x = abs (x - 2) <= 2 ;;
val test : int -> bool = <fun>
# List.filter test [4;1;7;3;8;9;2;0] ;;
- : int list = [4; 1; 3; 2; 0]
# 

List.filter is a function from the standard library. List.filter f l produces the list of elements of l for which f answers true.

Getting the function that decides if each element should go in the results list is orthogonal to the problem of filtering the list once you have this function, so you should do that first.

If you wish to use for f a function that is the transitive closure of a relation that you have, you can use the library ocamlgraph to obtain that transitive closure. Specifically, of these functions, use add_vertex for each puzzle piece, add_edge for each relation that you have, and then apply function transitive_closure to get a new graph g in which you can ask if there is an edge between two elements e1 and e2 with mem_edge g e1 e2. The partially applied function mem_edge g e1 can be passed to List.filter.

Answer 2

Your solution would not work, because it finds only the direct connected things. Suppose you have a list of mixed puzzle pieces. The test function will return true if and only a given piece A is pluggable with given piece B. The problem is, in your list there a puzzle pieces from different puzzles. What I need is a filter aka "filter all puzzle pieces which are related to this piece".

The function you suggested does not solve this problem.

Answer 3

Hmmm, I will try to refine my question...

1. there exists an unsorted list of things, pE. "let lst = [a;b;c;d;e;f;g;h];;" with type val a' list
2. there exists also a function which decide if two things are directly connectable or in other words, if the two things are direct neighbours: val test : a' -> a' -> bool
3. what I need is a function which has three arguments, the first one is a specific thing, the second one the unsorted list of things as suggested above, the last one is the test-function described above: val filter_connected : a' -> a' list -> (a' -> a' -> bool) -> a' list

if a <-> b are direct neigbours and b <-> c are direct neighbours then [a;b;c] are connected.

The suggested "List.filter () lst" does not help here, because it only filters the directed neighbours.

In the example above with a <-> b and b <-> c as direct neighbours in case of test-function, and all others not, the "filter_connected" call will be:

"filter_connected b lst (test);;"

and would return: [a;b;c]

Hope it will be more clean...