Спрашивая о типе возвращаемого значения, список и установить структуру данных в OCaml

Question

У меня есть функция для вычисления списка в булеву матрицу, где num_of_name: 'a list -> 'a -> int: возвращает позицию элемента в списке.

1) Я бы хотел mat_of_dep_rel : 'a list -> bool array array.

Моя проблема в том, что из первого List.iter должен быть список l, а не пустой список []. Но если я верну l вместо [], это даст мне тип: ('a * 'a list) list -> boolean array array. Это не то, что я хочу.

Я хотел бы знать, как я могу вернуть mat_of_dep_rel: 'a list -> bool array array?

let mat_of_dep_rel l =
  let n = List.length l in
  let m = Array.make_matrix n n false in
  List.iter (fun (s, ss) ->
    let i = num_of_name ss s in
    List.iter (fun t ->
      m.(i).( num_of_name ss t) <- true) ss) [];
  m;;

2) У меня есть другие функции для вычисления классов эквивалентности, для вычисления класса эквивалентности: проверьте элемент i, если у него есть путь i -> j и j -> i или он сам. Я хотел бы вернуть мне тип int list list. В этом коде я принудительно возвращаю тип возврата 'list list путём j в [j]. Мой вопрос:

Правильно ли, если я так силой заставлю? Если нет, то как я могу вернуть нужный тип int list list.

let eq_class m i =
     let mi = m.(i) in
     let aux = 
       List.fold_right (fun j l ->
     if j = i || mi.(j) && m.(j).(i) then
       [j] :: l else l) in
     aux [] [];;

Другая функция eq_classes вычисляет набор классов эквивалентности, собирая все классы эквивалентности. Я хотел бы использовать структуру данных списка больше, чем с помощью набора. Но на данный момент я не совсем понимаю, что код говорит здесь.

Не могли бы вы объяснить для меня? Если я хочу использовать структуру данных списка, как я могу ее использовать? Чем отличается список от заданной структуры данных в OCaml? Продвижение / Недостаток своего?

let eq_classes m =
  IntSet.fold (fun i l -> IntMap.add i (eq_class m i) l)
    IntSet.empty IntMap.empty;;

3) Мой последний вопрос: После всех классов эквивалентности я бы хотел их отсортировать. У меня есть другие функции

let cmp m i j = if eq_class m i = eq_class m j then 0
  else if m.(i).(j) then -1 else 1;;

let eq_classes_sort m l = List.sort (cmp m) l;;

для последней функции, которую я хочу вернуть для меня b ool array array -> int list list не bool array array -> int list -> int list

Спасибо за вашу помощь.

Answer 1

В ваших вопросах много неправильного или неясного, но я постараюсь ответить как можно лучше.

Вопрос 1

Вы, очевидно, пытаетесь преобразовать представление графа зависимостей из списка в матрицу.Не имеет никакого смысла иметь граф зависимостей, представленный в виде 'a list (на самом деле интересного способа построить булеву матрицу из произвольного списка в любом случае нет), так что вы, вероятно, намеревались использовать(int * int) list пар, каждая пара (i,j) является зависимостью i -> j.

Если вместо этого у вас есть ('a * 'a) list произвольных пар, вы можете легко пронумеровать элементы, используя функцию num_of_name, чтобы превратить его в вышеупомянутый (int * int) list.

Получив это, вы можете легко построить матрицу:

let matrix_of_dependencies dependencies =
  let n = List.fold_left (fun (i,j) acc -> max i (max j acc)) 0 dependencies in  
  let matrix = Array.make_matrix (n+1) (n+1) false in
  List.iter (fun (i,j) -> matrix.(i).(j) <- true) dependencies ;
  matrix

val matrix_of_dependencies : (int * int) list -> bool array array

Вы также можете вычислить параметр n вне функции и передать его.

Вопрос 2

Класс эквивалентности - это набор элементов, которые все эквивалентны.Хорошим представлением для набора в OCaml будет список (модуль List) или набор (модуль Set).Список-списки не является допустимым представлением для набора, поэтому у вас нет причин использовать его.

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

let equivalence_class matrix element = 
  let column = matrix.(element) and set = ref [] in
  Array.iteri begin fun element' dependency -> 
    if dependency then set := element' :: !set
  end column ;
  !set

val equivalence_class : bool array array -> int list

Я проверяю только на i -> j, потому что, если ваши зависимости действительно являются отношениями эквивалентности (рефлексивные, транзитивные, симметричные),тогда i -> j подразумевает j -> i.Если ваши зависимости не отношения эквивалентности, то вы на самом деле ищете циклы в графическом представлении отношения, который полностью отличается от того, что вы предложили, если только вы не вычислите переходныйсначала закройте вашего графика зависимостей.

Наборы и списки являются хорошо документированными стандартными модулями, а их документация свободно доступна в Интернете.Задавайте вопросы по StackOverflow, если у вас есть определенные проблемы с ними.

Вы попросили нас объяснить кусок кода, который вы предоставляете для eq_classes.Объяснение состоит в том, что он складывается на пустом множестве, поэтому он возвращает свое начальное значение - пустую карту.Это совершенно бессмысленно.Более подходящей реализацией будет:

let equivalence_classes matrix = 
  let classes = ref [] in 
  Array.iteri begin fun element _ ->
    if not (List.exists (List.mem element) !classes) then
      classes := equivalence_class matrix element :: !classes 
  end matrix ;
  !classes

val equivalence_classes : bool array array -> int list list

. Возвращает все классы эквивалентности в виде списка списков (каждый класс эквивалентности является отдельным списком).

Вопрос 3

Система типов указывает, что вы определили функцию сравнения, которая работает на int, поэтому вы можете использовать ее только для сортировки int list.Если вы намереваетесь отсортировать int list list (список классов эквивалентности), то вам нужно определить функцию сравнения для int list элементов.

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

let compare_classes matrix c c` = 
  match c, c` with 
    | h :: _, h' :: _ -> if matrix.(h).(h') then 1 else -1
    | _ -> 0 

let sort_equivalence_classes matrix = List.sort (compare_classes matrix)

Этот код предполагает, что 1. каждый класс эквивалентности появляется только один раз и 1. каждый класс эквивалентности содержит хотя бы один элемент.Оба предположения разумны при работе с классами эквивалентности, и это простой процесс, позволяющий заранее исключить дубликаты и пустые классы.