OCaml 옵션 값 트리

Question

주어진 트리를 ‘a option 요소 목록에 postfix 순서 (postorder)로 저장하는 ‘a btree -> ‘a option list 유형의 함수를 작성하는 작업이 있습니다.

내부 노드는 None으로 표시되고 외부 노드 (잎)는 x이며 Some x으로 표시됩니다.

지금까지 나뭇잎 용으로는 간단하지만 'a option list에 넣는 방법은 무엇입니까?

type 'a btree = L of 'a | N of 'a btree * 'a btree ;; 

let rec store t = 
    match t with 
     | L x -> Some x 
     | N (a,b) -> None ??? 
;; 

내가 알고있는 두 번째 대/소문자는 잘못되었지만 해결 방법은 무엇입니까?

Answer 1

첫 번째 사례를 살펴보면 그 사실도 알 수 있습니다. 'a option을 반환하지만이 함수는 'a option list을 반환해야합니다. 분명히

당신은 목록을 반환, 그래서 첫 번째 해결됩니다 : 이제 두 번째 경우를 해결하자 이제

let rec store = function 
    | L x -> [Some x] 
    | N (a,b) -> [None] (* ??? *) 

을; 우리는 우리의 출력에 None를 추가하기를 원하지만 그 전에, 우리는 우리의 하위 트리의 노드를 원하는 :

let rec store = function 
    | L x -> [Some x] 
    | N (a,b) -> (store a) @ (store b) @ [None] 

@는

'a list -> 'a list -> 'a list 

즉이 함께 목록을 조인 유형이 있습니다. 우리는 왼쪽 하위 트리의 결과 목록에 참여한 다음 오른쪽, 그리고 마지막으로이 내부 노드에 대한 결과 목록에 참여하려고합니다.

Answer 2

누군가가이 세분화에 관심이있는 경우, 추가 누적 기 매개 변수를 스레딩하여 Len 솔루션보다 조금 더 나은 성능을 발휘할 수 있습니다.

아이디어는 트리를 취하는 함수 store : 'a btree -> 'a option list에서 이동 매개 변수로 전달 된 기존 리스트 트리의 요소를 추가하는 기능 store' : 'a btree -> 'a option list -> 'a option list에리스트를 생성하는 것이다. 이 정의에

let rec store' t acc = match t with 
    | L x -> Some x :: acc 
    | N (a, b) -> 
    store' a (store' b (None :: acc)) 

이 요소 만 제는 임시 store a 목록을 작성하기 위해 사용하는 대신에, 최종 결과리스트에 한번 첨가되고, 다음 (@) 연산자를 통해 최종 결과로 두 번 첨부. acc 전에 t를 작성하는리스트의 최종 요소 순서의 직관을 제공하기 때문에

파라미터 순서가 중요하다 t의 요소 acc에 이미 존재하는 요소 전에 될 것이다. 이렇게하면 N 사례가 매우 자연스럽게 읽을 수 있습니다. 결과는 먼저 a, 그 다음 b, None, acc의 요소를 갖습니다.마지막으로

, 당신은 물론 store'의 측면에서 store를 정의 할 수 있습니다 :

let store t = store' t [] 

당신이 "낮은 수준을 노출하지 않으려는 경우 (두 번째 내부의 첫 번째 정의를 포장하는 관례 "기능) 따라서 내측 영역을 입력하지 않는) 사용자에게, 그리고 그것을 재귀 아니므로 충돌하지 않는 외부 정의와 같은 이름 (얻었다 : 물론

let store t = 
    let rec store t acc = match t with 
    | L x -> Some x :: acc 
    | N (a, b) -> 
     store a (store b (None :: acc)) 
    in store t [] 

여부 이 정의는 렌의 1 d보다 "더 좋다". 귀하의 평가 기준이 무엇인지 알려줍니다. Len의 솔루션은 더 짧고, 읽기 쉽고, 원래 문제를보다 면밀히 매핑합니다.

(당신은 대신 엄격한 목록의 게으른 열거를 사용하여 두 세계의 최고를 얻을 수 있지만, 그것은 또 다른 이야기.이다) 그런데