时间戳

首页 > 解决方案 > Ocaml 和返回类型（图论）

ocaml - Ocaml 和返回类型（图论）

问题描述

我只是 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

（alreadyseen 是一个布尔向量，之前定义过）

我唯一的问题是我希望函数返回lst修改后的列表（在循环中），此时，它是一个单位函数。

我试图将 lst 定义为参考，但后来我不知道如何返回它......

我希望它更清楚，我目前对这一切都不熟悉......

谢谢 ！

标签： ocamlgraph-theoryreturn-type

解决方案

这是您的代码的降级版本，它演示了一种方法来做您想做的事。

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.

推荐阅读