Memfilter hal-hal yang terhubung secara langsung dan tidak langsung dari daftar

jika Anda memiliki fungsi "test a b" yang mengembalikan nilai true jika a dan b terhubung secara langsung dan jika Anda memiliki daftar hal-hal yang tidak berurutan, apa solusi yang elegan dan cepat untuk memfilter semua hal yang terhubung dari daftar yang diberikan?

Contoh:

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]

Ada petunjuk?

Hmmm, saya akan mencoba memperjelas pertanyaan saya...

  1. ada daftar hal-hal yang tidak disortir, pe. "biarkan lst = [a;b;c;d;e;f;g;h];;" dengan tipe val a' daftar
  2. terdapat juga fungsi yang memutuskan apakah dua hal dapat dihubungkan secara langsung atau dengan kata lain, jika kedua hal tersebut bertetangga langsung: val test : a' -> a' -> bool
  3. yang saya butuhkan adalah fungsi yang memiliki tiga argumen, yang pertama adalah hal yang spesifik, yang kedua adalah daftar hal-hal yang tidak disortir seperti yang disarankan di atas, yang terakhir adalah fungsi pengujian yang dijelaskan di atas: val filter_connected : a' -> a ' daftar -> (a' -> a' -> bool) -> a' daftar

jika a ‹-> b bertetangga langsung dan b ‹-> c bertetangga langsung maka [a;b;c] terhubung.

"List.filter () lst" yang disarankan tidak membantu di sini, karena hanya memfilter tetangga yang diarahkan.

Pada contoh di atas dengan a ‹-> b dan b ‹-> c sebagai tetangga langsung jika ada fungsi uji, dan yang lainnya tidak, panggilan "filter_connected" akan menjadi:

"filter_connected b pertama (tes);;"

dan akan kembali: [a;b;c]

Semoga semakin bersih...


list filter components ocaml
person Andreas Romeyke    schedule 15.03.2010    source sumber
comment
Saya cukup yakin maksud Anda diff = 0 di mana Anda menulis diff == 0, jika hanya karena mereka melakukan hal yang sama dalam implementasi saat ini. Tapi sekali lagi, jika test adalah contoh dari apa yang Anda maksud dengan terhubung, mengapa Anda tidak meneruskannya ke filter_connected dan yang lebih penting, bukankah definisi keterhubungan itu hanyalah kesetaraan dan bagaimana cara menggunakannya untuk mendapatkan [4;1;3;2;0]?   -  person Pascal Cuoq    schedule 15.03.2010
comment
paste kode anda, dan silahkan format untuk mendapatkan jawaban yang lebih baik (jika ada jawaban yang lebih baik dari Pascal)   -  person LB40    schedule 16.03.2010

Jawaban (1)


arrow_upward
3
arrow_downward

Saya berasumsi Anda ingin mendapatkan elemen daftar asli yang jaraknya kurang dari 2 dari 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 adalah fungsi dari perpustakaan standar. List.filter f l menghasilkan daftar elemen l yang f menjawab true.

Mendapatkan fungsi yang memutuskan apakah setiap elemen harus masuk dalam daftar hasil adalah ortogonal terhadap masalah memfilter daftar setelah Anda memiliki fungsi ini, jadi Anda harus melakukannya terlebih dahulu.

Jika Anda ingin menggunakan untuk f fungsi yang merupakan penutupan transitif dari suatu relasi yang Anda miliki, Anda dapat menggunakan pustaka ocamlgraph untuk mendapatkan penutupan transitif tersebut. Khususnya, dari fungsi-fungsi ini, gunakan add_vertex untuk setiap potongan puzzle, add_edge untuk setiap potongan puzzle relasi yang Anda miliki, lalu terapkan fungsi transitive_closure untuk mendapatkan grafik baru g di mana Anda dapat menanyakan apakah ada tepi antara dua elemen e1 dan e2 dengan mem_edge g e1 e2. Fungsi yang diterapkan sebagian mem_edge g e1 dapat diteruskan ke List.filter.

person Pascal Cuoq    schedule 15.03.2010
comment
+1: untuk menyebutkan ocamlgraph, suka lib ini, namun butuh beberapa saat bagi saya untuk memahaminya. :-) - person LB40; 16.03.2010