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

если у вас есть функция «test a b», которая возвращает истину, если 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. "let lst = [a; b; c; d; e; f; g; h] ;;" с типом val a 'list
  2. существует также функция, которая определяет, могут ли две вещи соединяться напрямую или, другими словами, если две вещи являются прямыми соседями: val test: 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 в качестве прямых соседей в случае тестовой функции, а для всех остальных - нет, вызов "filter_connected" будет:

"filter_connected b lst (test) ;;"

и вернет: [a; b; c]

Надеюсь, будет чище ...


list filter components ocaml
person Andreas Romeyke    schedule 15.03.2010    source источник
comment
Я почти уверен, что вы имеете в виду diff = 0, где написали diff == 0, хотя бы потому, что они делают то же самое в текущих реализациях. Но опять же, если test - это пример того, что вы подразумеваете под соединением, почему вы не передаете его в filter_connected и, что более важно, не является ли это определение связанности просто равенством и как его использовать для получения [4;1;3;2;0]?   -  person Pascal Cuoq    schedule 15.03.2010
comment
вставьте свой код и отформатируйте его, чтобы получить лучшие ответы (если есть лучший ответ, чем у Паскаля)   -  person LB40    schedule 16.03.2010

Ответы (1)


arrow_upward
3
arrow_downward

Я предполагаю, что вы хотите получить элементы исходного списка, которые находятся на расстоянии менее 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.

person Pascal Cuoq    schedule 15.03.2010
comment
+1: за упоминание ocamlgraph, мне нравится эта библиотека, хотя мне потребовалось время, чтобы понять. :-) - person LB40; 16.03.2010