Императивная структура данных OCaml с указателями?

Возможно ли такое?

Всем привет,

в моем классе нам сказали реализовать двоичные деревья поиска в OCaml, используя функциональное и императивное программирование. Мы следуем ADT и реализации на Pascal, процедурном языке, где используются указатели.

Вот как выглядит структура данных:

# Pascal
type
   tKey      = integer;
   tPos      = ^tNode;
   tNode     = record
          key         : tKey;
          left, right : tPos;
           end;      
   tBST = tPosT;

Нам также дали некоторые основные операции BST. Вот пример одного из них, если это может помочь:

# Pascal
procedure add_key(VAR T : tBST; k:tKey);
var new, parent, child :  tBST;
begin
   createNode(new);
   new^.key := k;
   new^.left := nil;
   new^.right := nil;

   if T=nil then
      T := new
   else begin
      parent := nil;
      child := T;
      while (child <> nil) and (child^.key <> k) do begin
     parent := child;
     if k < child^.key then
        child := child^.left
     else
        child := child^.right;
      end;

      if (child = nil) then 
     if k < parent^.key then
        parent^.left := new
     else
        parent^.right := new;
        { duplicates are ignored }
   end;
end;

Вот как выглядит моя функциональная (если это имеет смысл) структура данных:

type key =
    Key of int;;

type bst = 
    Empty   
    | Node of (key * bst * bst);;

Однако у меня большие проблемы с использованием императивного аспекта OCaml. Я должен сделать его максимально похожим на реализацию Pascal, и я не знаю о возможностях структур данных и указателей в OCaml, так как я всегда программировал с использованием рекурсии и так далее. Я думал об использовании нескольких «пусть», если и еще, но я понятия не имею, как определить свою структуру данных. Был бы признателен за огромный вклад в это.


pointers abstract-data-type ocaml imperative
person deko    schedule 26.09.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Насколько я понимаю, у вас будет такой тип:

type key = int

type t = Empty | Node of t * key * t

Но ваша функция добавления не должна выглядеть так:

let rec add x t =
  match t with
    | Empty ->
      Node (Empty, x, Empty)
    | Node (l, v, r) ->
      let c = compare x v in
      if c = 0 then t
      else if c < 0 then Node (add x l, v, r)
      else Node (l, v, add x r)

Потому что это только функционально.

Возможно, вы могли бы изменить свой тип на:

type t = Empty | Node of t ref * key * t ref

И попробуйте адаптировать функцию add к этому типу.

person Lhooq    schedule 26.09.2017
comment
Могу я спросить, что еще? используется ли он для абстрагирования значения узла? Да, в основном то, что вы сказали, это то, что происходит. Мой тип должен быть максимально похож на паскаль. Не только то, как это работает. Я попробую с твоим типом, а пока продолжу расследование. - person deko; 27.09.2017
comment
Плохая копия/вставка ;-) Я обновил свой ответ, так как он должен быть key - person Lhooq; 27.09.2017