2017-10-10 16 views
0

OCaml에서 큐 구조를 구현하려고 시도하고 있으며 현재 값이 큐에 있는지 테스트하는 함수를 작성하고 있습니다. 필자는 원래 올바른 것을 썼다. 또는 최소한 그것이 기능의 올바른 구현이라고 생각한다. 하지만 테스트했을 때 예기치 않은 테스트 실패가 발생했습니다. 즉, 큐가 비었을 때 false를 리턴하지만, 다른 모든 경우, 큐가 비 었는지 여부, 그리고 큐가 값을 포함하는지 여부를 false로 리턴합니다. 그래서 나는 이런 종류의 벙어리 방식으로 함수를 다시 작성하여 (Some h -> true) 문제가 무엇인지 알아 내려고합니다. 이 멍청한 기능을 사용하더라도, 큐와 값을 전달할 때 여전히 false를 리턴하므로 None이든 아니든간에 모든 큐의 헤드를 None으로 읽는 것이 분명합니다.패턴 매칭에서 OCaml 이상한 동작

은 포함 :

let contains (v: 'a) (q: 'a queue) : bool = 
    if not (valid q) then failwith "contains: given invalid queue"; 
    let rec loop (value: 'a) (qn: 'a qnode option) : bool = 
     begin match qn with 
     | None -> false 
     | Some h -> true 
     end 
    in loop elt q.head 

테스트

let test() : bool = 
    let q = create() in 
    not (contains 1 q) 
    ;; run_test "contains empty" test 

    let test() : bool = 
    let q = from_list [2; 3] in 
    contains 3 q 
    ;; run_test "contains non-empty true" test 

    let test() : bool = 
    let q = from_list [2; 3] in 
    not (contains 4 q) 
    ;; run_test "contains non-empty false" test 

테스트 예상대로 나와있다 여기에 기록 된 다른 기능. 대기열 유형의 유형 선언은 감사하겠습니다 None로 모든 q.head을 복용하는 이유에 대해

type 'a qnode = { v: 'a; 
        mutable next: 'a qnode option } 

    type 'a queue = { mutable head: 'a qnode option; 
        mutable tail: 'a qnode option } 

어떤 생각이다.


from_list

qnode으로 각각의 값을 선회하고, 생성 된리스트를 리턴 다음에 연결 목록을 안내 도우미 함수.

let rec vals_to_qnodes (l: 'a list) : 'a qnode list = 
    begin match l with 
    | [] -> [] 
    | [h] -> [{v = h; next = None}] 
    | h1::h2::t -> let sofar = vals_to_qnodes (h2::t) in 
        begin match sofar with 
        | [] -> [] 
        | x::y -> {v = h1; next = Some x}::x::y 
        end 
    end 

q 노드 목록을 만들고 첫 번째 요소와 마지막 요소를 찾고 큐의 머리와 꼬리로 할당하십시오.

let from_list (l: 'a list) : 'a queue = 
    let qsList = vals_to_qnodes l in 
    begin match qsList with 
    | [] -> create() 
    | h::t -> begin match t with 
       | [] -> {head = Some h; tail = Some h} 
       | h2::t2 -> let x = List.rev t2 in 
          begin match x with 
          | [] -> {head = None; tail = None;} 
          | h3::t3 -> {head = Some h; tail = Some h3} 
          end 
       end 
    end 

는 여기에 내가 원래 내가 이상한 행동에 좁힐를 단순화하기 위해 시도하기 전에이 기능을 포함에 대해서 가지고 있던거야.

let contains (v: 'a) (q: 'a queue) : bool = 
    if not (valid q) then failwith "contains: given invalid queue"; 
    let rec loop (value: 'a) (qn: 'a qnode option) : bool = 
    begin match qn with 
    | None -> false 
    | Some h -> if v == value then true 
       else loop value h.next 
    end 
    in loop v q.head 

답변

2

내가 코드를하려고하면 그것은 당신이 설명하는대로 작동하지 않습니다

# let n = { v = 1; next = None };; 
val n : int qnode = {v = 1; next = None} 
# let q = { head = Some n; tail = Some n };; 
val q : int queue = 
    {head = Some {v = 1; next = None}; tail = Some {v = 1; next = None}} 
# contains 3 q;; 
- : bool = true 

그래서, 대답은 실제로 반환하는 것을 from_list에 따라 달라집니다 말하고 싶지만.

부연 설명으로, contains의 정의는 내가 볼 수있는대로 정의되지 않은 elt에 대한 참조를 가지고 있습니다.

업데이트

새 코드는 create를 정의하지 않습니다.나는 create이 정의를 공급 : 머리가 None :-)에게 내가 '

+0

것으로 보인다 이유

# from_list [1;2];; - : int queue = {head = None; tail = None} 

이 설명합니다 :

let create() = { head = None; tail = None } 

내가 from_list [1;2]를 실행하면, 이것은 내가 볼 것입니다 게시물을'from_list'의 내용으로 업데이트합니다. 'contains' 함수는 나의 ​​벙어리 재 작성 때문에'elt' 값을 사용하지 않습니다. 또한 원래 코드가 포함 된 내용을 게시 할 것입니다. – Addem

+0

'from_list' 함수는 길이 2의리스트가 전달 될 때 빈 큐를 리턴합니다. –