Ocaml和and类型(图论)

Question

我只是Ocaml的乞丐，我想学习图论，但是用Ocaml实现。我很难做一些事情:我只是想用深度优先搜索来列出一个图的连通成分。所以，我做了

#open "stack" ;;

let non_empty pile = 
    try push (pop pile) pile ; true with Empty -> false ;;


let connected_comp g = 
    let already_seen = make_vect (vect_length g) false in
    let comp = [] in

    let dfs s lst = 
        let totreat = new () in
        already_seen.(s) <- true; push s totreat;

        let rec add_neighbour l = match l with
            | [] -> ()
            | q::r when already_seen.(q) = false -> push q totreat; already_seen.(q) <- true; add_neighbour r
            | q::r -> add_neighbour r
        in

        while non_empty totreat do
            let s = pop totreat in
            already_seen.(s) <- true;
            (* we want to add s to the list lst *) s::lst;
            add_neighbour g.(s);
        done
    in  


    let rec head_list l = match l with
        | [] -> failwith "Empty list"
        | p::q -> p
    in  
    let rec aux comp t = match t with
        | t when t = vect_length g -> comp
        | t when already_seen.(t) = true -> aux comp (t+1)
        | t -> aux ((dfs t [])::comp) (t+1) (* we want that dfs t [] return the list lst modified *)
    in aux comp 0;;

我得到了：

>       | t -> (dfs t [])::comp ; aux  comp (t+1) (* we want that dfs t [] return the list lst modified *)
>              ^^^^^^^^^^^^^^^^
Warning : this expression is of type unit list,
but is used with the type unit.
connected_comp : int list vect -> unit list = <fun>
- : unit list = []
- : unit = ()

当然，我一点也不惊讶。但是我想要做的是，函数dfs返回在参数上发送的列表( lst列表)，但是修改了，这里不是这样的，因为函数的类型是单位，因为它没有返回任何内容。但是在Ocaml中，由于语言是用来返回我认为的最后一个表达式，所以我不知道该怎么做。我也可以对dfs函数使用递归算法，因为通过过滤，它将允许我返回列表，但我只想了解Ocaml，并对算法进行了修改(即使不是最优的)。

有人能帮我吗？

编辑:，正如我们问我的，我将尽量减少我的代码，并切入要点。所以，我有一个函数dfs，它对应于深度优先搜索(对于图)

let dfs s lst = 
    let totreat = new () in
    already_seen.(s) <- true; push s totreat;

    let rec add_neighbour l = match l with
        | [] -> ()
        | q::r when already_seen.(q) = false -> push q totreat; already_seen.(q) <- true; add_neighbour r
        | q::r -> add_neighbour r
    in

    while non_empty totreat do
        let s = pop totreat in
        already_seen.(s) <- true;
        (* we want to add s to the list lst *) s::lst;
        add_neighbour g.(s);
    done
in

(已经看到的是以前定义的布尔向量)

我唯一的问题是，我希望函数返回修改过的列表lst (在循环中)，此时它是一个单元函数。

我试着把第一条定义为参考，但后来我不知道怎么回事.

我希望这更清楚，我现在对这一切并不熟悉.

谢谢！

Answer 1

下面是您代码的降级版本，它演示了一种实现您想要的功能的方法。

let non_empty _ = false

let dfs s lst =
  let local_lst = ref lst in

  while non_empty () do
    (*do stuff here*)
    let s = 1 in
    local_lst := s::!local_lst;
    (*do stuff here*)
  done;
  !local_lst

我首先将一个本地可变值local_lst初始化为作为参数给出的列表lst。然后在while循环中更新这个值。最后，我返回存储在local_lst中的值。