Генерация кода для работы со совпадениями на регулярных древовидных структурах?

Question

Я занимаюсь разработкой специализированного дерева квадов для биоинформатики. Типы для qtree:

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);;

Теперь, чтобы сделать совпадение на этих деревьях, когда вы строите или гуляете, вы получите что-то вроде:

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)) ->
...

Вы понимаете, в основном мне нужно охватить все 16 комбинаций (4 поддерева, которые могут быть либо пустыми, либо Nd). Это много печатать, и это подвержено ошибкам.

Тем не менее, это очень регулярная структура, которая поддается генерации кода. Я собирался сгенерировать этот код, используя скрипт Ruby, но мне интересно, возможно ли это с помощью campl4 или новых макросов в стиле -ppx (из-за отсутствия лучшего термина)? И если так, как я мог начать в любом из этих направлений?

Answer 1

В функционально-идиоматическом дереве каждый узел является корнем своего поддерева, даже если каждый другой узел в этом поддереве пуст. Вы захотите свернуть явное определение ROOT и объединить свойство counter с конечным узлом:

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

Но тогда, пока вы это делаете, вы можете просто сделать этот ref явным int, чтобы вы могли использовать постоянные структуры данных:

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)
     ...