询问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).list-of-lists不是集合的有效表示,因此您没有理由使用它.

你的算法很模糊,因为你显然在空列表上执行折叠,这只会返回初始值(空列表).我假设您打算迭代遍历矩阵列中的所有条目.

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