3

我正在开发一个专门的四叉树来做一些生物信息学。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 样式“宏”（因为没有更好的术语）？如果是这样，我怎么能从这两个方向开始呢？

4

1 回答 1

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)
     ...
于 2015-04-18T11:07:14.890 回答