Ocaml и тип возврата (теория графов) - PullRequest
Новая
       89

Ocaml и тип возврата (теория графов)

0 голосов
/ 13 июня 2018

Я только начинающий в 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), но измененный, и здесь дело обстоит не так, поскольку функция имеет тип unit, потому что она ничего не возвращает.Но в Окамле, поскольку язык создан для возврата последнего выражения, я думаю, я не знаю, как это сделать.Я мог бы также использовать рекурсивный алгоритм для функции 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, модифицированный (в цикле while), когда в этот момент это единичная функция.

Я попытался определить lst как ссылку, но затемЯ не знаю, как его вернуть ...

Надеюсь, это более понятно, на данный момент я не знаком со всем этим ...

Спасибо!

1 Ответ

0 голосов
/ 13 июня 2018

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

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.

...