일반 나무와 같은 구조에서 일치를 처리하기위한 코드 생성?

Question

저는 몇 가지 생물 정보학을위한 특수화 된 쿼드 트리를 개발 중입니다. qtree에서의 유형은 다음과 같습니다 당신은 아이디어를 얻을

let rec add_node base k qtree = 
    let rec aux k' accum qtree' = 
    if k' = k then 
    match qtree' with 
    | Nd(bse, Empty, cc, gg, tt) -> Nd(bse, (Leaf(ref accum)),cc,gg,tt) 
    | Nd(bse, aa, Empty, gg, tt) -> Nd(bse, aa,(Leaf(ref accum)),gg,tt) 
    | Nd(bse, aa, cc, Empty, tt) -> Nd(bse, aa,cc,(Leaf(ref accum)),tt) 
    | Nd(bse, aa, cc, gg, Empty) -> Nd(bse, aa,cc,gg,(Leaf(ref accum))) 
    | Leaf _ -> qtree' 
    | Empty -> Leaf(ref accum) 
    | _ -> qtree' 
else 
match qtree' with 
| Leaf(iref) -> iref := !iref + 1; qtree'       
| Nd(bse, Empty,Empty,Empty,Empty) -> (*all empty*) 
    (
    match base with 
    | A -> Nd(bse,(new_node base),Empty,Empty,Empty) 
    | C -> Nd(bse,Empty,(new_node base),Empty,Empty) 
    | G -> Nd(bse,Empty,Empty,(new_node base),Empty) 
    | T -> Nd(bse,Empty,Empty,Empty,(new_node base)) 
    | _ -> qtree' 
    ) 
... 
| Nd(bse, Empty,(Nd(_,_,_,_,_) as c),(Nd(_,_,_,_,_) as g),(Nd(_,_,_,_,_) as t)) -> 
    (
    match base with 
    | A -> Nd(bse,(new_node base),(aux (k'+1) (accum+1) c),(aux (k'+1) (accum+1) g),(aux (k'+1) (accum+1) t)) 
    | C -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t)) 
    | G -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t)) 
    | T -> Nd(bse,Empty,(aux (k'+1)(accum+1) c),(aux (k'+1)(accum+1) g),(aux (k'+1)(accum+1) t)) 
    | _ -> qtree' 
    ) 
... 
| Nd(bse, (Nd(_,_,_,_,_) as a),(Nd(_,_,_,_,_) as c),(Nd(_,_,_,_,_) as g),(Nd(_,_,_,_,_) as t)) -> 
... 

, 기본적으로 내가 필요 : 중 건설 또는 뭔가와 끝까지 걸을 때

이제

type base = A | C | G | T | ROOT ;; 
type quad_tree = Nd of bases * quad_tree * quad_tree * quad_tree * quad_tree 
      | Empty 
      | Leaf of int ref ;; 

let init_quad_tree = Nd(ROOT, Empty,Empty,Empty,Empty);; 
let new_node b = Nd(b,Empty,Empty,Empty,Empty);; 

이 나무 된 경기를 할 거기에 16 개의 모든 조합을 포함합니다 (비어 있거나 Nd 일 수있는 4 개의 하위 트리). 그것은 많은 타이핑이고 오류가 발생하기 쉽습니다.

그러나 코드 생성에 도움이되는 매우 규칙적인 구조입니다. Ruby 스크립트를 사용하여이 코드를 실제로 생성하려고했으나 campl4 또는 새로운 -ppx 스타일의 "매크로"(더 나은 용어가없는 경우)를 사용할 수 있는지 궁금합니다. 그렇다면 어떻게 그 방향 중 하나에서 시작할 수 있습니까?

Answer 1

기능적 관용적 인 트리에서 노드는 해당 하위 트리의 다른 모든 노드가 비어 있더라도 해당 하위 트리의 루트입니다.

type base = A | C | G | T ;; 
type quad_tree = 
    | Node of base * int ref * quad_tree * quad_tree * quad_tree * quad_tree 
    | Empty 

그러나 당신이 그것에있는 동안 당신은뿐만 아니라 그냥 심판이 그렇게 명시 적 INT 만들 수 있습니다 당신은 명시 적 ROOT 정의를 축소하고, 리프 노드에 카운터 속성에 병합 할 수 있습니다 당신이 영구 데이터 구조를 사용할 수 있습니다 :

type quad_tree = 
    | Node of base * int * quad_tree ... 
    | Empty 

워킹을/당신이 원하는 무엇에 대한 이해를 기반으로하는 복잡 할 필요가 없습니다 건설 (해당 경로와 일치하는 문자열을 나타내는 각 노드를 정확히) - - 매번 새로운 버전의 나무를 만들어 보자. 좀 못생긴 버전 :

let shorter str = String.sub 1 ((String.len str) - 1);; 

let rec add_str base str = match base with 
    | Empty -> 
    let ch = String.get str 0 in 
    if ch = 'A' then add_str Node('A', 0, Empty, Empty, Empty, Empty) (shorter str) 
    else if ch = 'C' then add_str Node('C', 0, Empty, Empty, Empty, Empty) (shorter str) 
    ... 
    | Node(b, v, aa, cc, gg, tt) -> 
    let len = String.length str in 
    if len = 0 then Node(b, v + 1, aa, cc, gg, tt) else 
    let ch = String.get str 0 in 
    if ch = 'A' then match aa with 
     | Empty -> Node(b, v, (add_str Empty str), cc, gg, tt) 
     | Node(b', v', ... , tt') -> add_str Node(b', v', ... , tt') (shorter str) 
    else if ch = 'C' then match cc with 
     | Empty -> Node(b, v, aa, (add_str Empty str), gg, tt) 
     | Node(b', v', ... , tt') -> add_str Node(b', v', ... , tt') (shorter str) 
    ...