Фильтрация прямо и косвенно связанных вещей из списка

Question

если у вас есть функция «test ab», которая возвращает true, если a и b связаны напрямую, и если у вас есть заданный неупорядоченный список вещей, что было бы элегантным и быстрым решением для фильтрации всех связанных вещей из данного списка?

Пример:

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]

Есть подсказки?

---

Хммм, постараюсь уточнить свой вопрос ...

1. существует несортированный список вещей, pE. "пусть lst = [a; b; c; d; e; f; g; h] ;;" с типом val a 'list
2. существует также функция, которая определяет, являются ли две вещи связанными напрямую или, другими словами, являются ли две вещи прямыми соседями: val тест: a '-> a' -> bool
3. мне нужна функция, которая имеет три аргумента, первый - это конкретная вещь, второй - несортированный список вещей, как предложено выше, последний - тестовая функция, описанная выше: val filter_connected: список a '-> a' -> (a '-> a' -> bool) -> a 'список

если a <-> b являются прямыми соседями, а b <-> c - прямыми соседями, то [a; b; c] связаны.

Предлагаемый «List.filter () lst» здесь не помогает, поскольку он фильтрует только направленных соседей.

В приведенном выше примере с a <-> b и b <-> c в качестве прямых соседей в случае test-функции, а все остальные нет, вызовом filter_connected будет:

"filter_connected b lst (test) ;;"

и вернется: [А, Ь; с] * +1027 *

Надеюсь, он будет более чистым ...

Answer 1

Я предполагаю, что вы хотите получить элементы исходного списка, которые находятся на расстоянии менее 2 от 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 - это функция из стандартной библиотеки. List.filter f l создает список элементов l, для которых f отвечает true.

Получение функции, которая решает, должен ли каждый элемент попадать в список результатов, ортогонально проблеме фильтрации списка, когда у вас есть эта функция, поэтому вы должны сделать это в первую очередь.

Если вы хотите использовать для f функцию, которая является транзитивным замыканием вашего отношения, вы можете использовать библиотеку ocamlgraph , чтобы получить это транзитивное замыкание. В частности, из этих функций используйте add_vertex для каждого кусочка головоломки, add_edge для каждого отношения, которое у вас есть, а затем примените функцию transitive_closure, чтобы получить новый график g, в котором вы можете спросите, есть ли грань между двумя элементами e1 и e2 с mem_edge g e1 e2. Частично примененная функция mem_edge g e1 может быть передана в List.filter.