포인터가있는 명령형 OCaml 데이터 구조?

Question

그런 것이 가능합니까? 내 수업에서

안녕 모두,

는 우리는 기능과 명령형 프로그래밍을 사용하여, OCaml의 이진 검색 나무를 구현하는 들었다. 우리는 포인터가 사용되는 절차 언어 인 파스칼에서 ADT와 구현을 따르고 있습니다.

# 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의 명령형 패싯을 사용한다. 가능한 한 파스칼 구현처럼 보이게해야하고, 재귀 적으로 항상 프로그래밍했기 때문에 OCaml에서 데이터 구조와 포인터의 가능성에 대해 알지 못합니다. 여러 개의 "let", if와 else 's를 사용하려고 생각했지만 데이터 구조를 정의하는 방법을 모릅니다. 엄청난 의견을 보내 주시면 감사하겠습니다. 난 당신이 유형이 같은 것 이해하는 것과

Answer 1

:

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 기능을 적용하려고합니다.