询问OCaml中的返回类型，列表和设置数据结构 [英] Asking about return type, list and set data structure in OCaml

问题描述

我有一个函数，可以将列表计算为布尔矩阵，其中num_of_name: 'a list -> 'a -> int:返回元素在列表中的位置.

I have a function compute a list to boolean matrix where num_of_name: 'a list -> 'a -> int : return a position of element in a list.

1)我想要mat_of_dep_rel : 'a list -> bool array array.

我的问题是，从第一个List.iter开始，它应该包含一个列表l，而不是一个空列表[].但是，如果我返回l而不是[]，它将为我提供一种类型:('a * 'a list) list -> boolean array array.这不是我想要的.

My problem is that from the first List.iter it should take a list l and not an empty list []. But if I return l instead of [], it will give me a type: ('a * 'a list) list -> boolean array array. Which is not what I want.

我想知道如何退回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.在这段代码中，我通过在[j].中放置j来强制返回类型'list list.我的问题是:

2) I have another functions compute equivalence classes, to compute an equivalence class : check an element i if it has a path i -> j and j -> i or itself. I would like it return for me a type int list list. In this code I force the return type 'list list by put j in [j]. My question is:

如果我这样强迫是正确的吗?如果没有，我该如何返回我想要的类型int list list.

Is it correct if I force like that? If not how can I return the type I want 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通过收集所有等效类来计算一组等效类.我想使用列表数据结构而不是使用集合.但是目前，我对这里的代码还不太了解.

Another function eq_classes compute a set of equivalence classes by collect all the equivalence class. I would like to use a list data structure more than using a set. But for the moment, I am not really understand about the code saying here.

能给我解释一下吗?如果要使用列表数据结构，该如何使用? OCaml中的列表和集合数据结构之间有什么区别?前进/后退?

Could you please explain for me? If I want to use a list data structure, how can I use it? What is a different between a list and a set data structure in OCaml? Advance/Disadvance of its?

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

3)我的最后一个问题是.在拥有所有等价类之后，我想对它们进行排序.我还有另一个功能

3) My last question is that. After having all the equivalence classes I would like to sort them. I have another functions

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

for the last function I want it return for me bool array array -> int list list not bool array array -> int list -> int list

谢谢您的帮助.

推荐答案

关于您的问题有很多错误或难以理解的地方，但是我会尽力回答.

There are quite many things wrong or obscure about your questions, but I'll try to answer as well as possible.

您显然正在尝试将依赖关系图的表示形式从列表转换为矩阵.将依赖关系图表示为'a list没有任何意义(实际上，没有有趣的方法可以从任意列表构建布尔矩阵)，因此您可能打算使用成对的(int * int) list，每对(i,j)是依赖项i -> j.

You're apparently trying to transform the representation of a dependency graph from a list to a matrix. It does not make any kind of sense to have a dependency graph represented as 'a list (in fact, there is no interesting way to build a boolean matrix from an arbitrary list anyway) so you probably intended to use an (int * int) list of pairs, each pair (i,j) being a dependency i -> j.

如果您有任意对的('a * 'a) list，则可以使用num_of_name函数轻松地将元素编号为上述的(int * int) list.

If you instead have a ('a * 'a) list of arbitrary pairs, you can easily number the elements using your num_of_name function to turn it into the aforementioned (int * int) list.

有了这个，就可以轻松构造一个矩阵:

Once you have this, you can easily construct a matrix :

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并将其传递给

You can also compute the parameter n outside the function and pass it in.

等效类是一组等效的元素.在OCaml中，集合的一个好的表示形式是列表(模块List)或集合(模块Set).列表列表不是一组的有效表示，因此您没有理由使用一个列表.

An equivalence class is a set of elements that are all equivalent. A good representation for a set, in OCaml, would be a list (module List) or a set (module Set). A list-of-lists is not a valid representation for a set, so you have no reason to use one.

您的算法是晦涩的，因为您显然是在一个空列表上执行折叠，这只会返回初始值(一个空列表).我假设您打算对矩阵列中的所有条目进行迭代.

Your algorithm is obscure, since you're apparently performing a fold on an empty list, which will just return the initial value (an empty list). I assume that you intended to instead iterate over all entries in the matrix column.

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.如果您的依赖关系不是等价关系，那么实际上您是在关系的图形表示中寻找循环，这与您建议的算法完全不同，除非您计算首先是依存关系图的传递闭包.

I only check for i -> j because, if your dependencies are indeed an equivalence relationship (reflexive, transitive, symmetrical), then i -> j implies j -> i. If your dependencies are not an equivalence relationship, then you are in fact looking for cycles in a graph representation of a relationship, which is an entirely different algorithm from what you suggested, unless you compute the transitive closure of your dependency graph first.

集和列表都是文档齐全的标准模块，并且它们的文档可在线免费获得.如果您遇到特定于 的问题，请在StackOverflow上提问.

Sets and lists are both well-documented standard modules, and their documentation is freely available online. Ask questions on StackOverflow if you have specific issues with them.

您要求我们解释您为eq_classes提供的代码段.原因是它在一个空集合上折叠，因此它返回其初始值-一个空映射.因此，这是完全没有意义的.一个更合适的实现是:

You asked us to explain the piece of code you provide for eq_classes. The explanation is that it folds on an empty set, so it returns its initial value - an empty map. It is, as such, completely pointless. A more appropriate implementation would be:

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

这将所有等效类作为列表返回(每个等效类是一个单独的列表).

This returns all the equivalence classes as a list-of-lists (each equivalence class being an individual list).

类型系统指出您已经定义了一个可在int上使用的比较函数，因此只能使用它对int list进行排序.如果打算对int list list(等效类列表)进行排序，则需要为int list元素定义一个比较函数.

The type system is pointing out that you have defined a comparison function that works on int, so you can only use it to sort an int list. If you intend to sort an int list list (a list of equivalence classes), then you need to define a comparison function for int list elements.

假设(如上所述)您的依存关系图是传递封闭的，您要做的就是使用现有的比较算​​法，并将其应用于每个类的任意代表:

Assuming that (as mentioned above) your dependency graph is transitively closed, all you have to do is use your existing comparison algorithm and apply it to arbitrary representants of each class:

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.每个等效类至少包含一个元素.这两个假设在使用等价类时都是合理的，并且这是一个事先消除重复和空类的简单过程.

This code assumes that 1. each equivalence class only appears once and 1. each equivalence class contains at least one element. Both assumptions are reasonable when working with equivalence classes, and it is a simple process to eliminate duplicates and empty classes beforehand.

这篇关于询问OCaml中的返回类型，列表和设置数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！