复杂数据结构ocaml上的模式匹配

Question

我是OCaml的新手,所以我在基础知识方面遇到了一些麻烦.对于我的程序,我必须将核苷酸与其补体(G - > C,C - > G,A - > T,T - > A)匹配,以便找到双螺旋的另一半.一般的想法是DNA由2个互补的螺旋组成,每个螺旋都是核苷酸序列.目前,我正在尝试计算双螺旋的另一半.

到目前为止,我已经用枚举代表核苷酸,并且我用一个核苷酸列表代表DNA,该核苷酸列表对应于一个螺旋.

type nucleotide = 
| G 
| C 
| A 
| T

type helix = nucleotide list

let rec complementary_helix (x:helix): helix =
| [G] -> [C]
| [C] -> [G]
| [A] -> [T]
| [T] -> [A]
end

我知道这里缺少一些东西,但我不知道如何去做.有人能引导我朝着正确的方向前进吗？

Answer 1

你基本上只是缺少List.map:

let complement = function
| G -> C
| C -> G
| A -> T
| T -> A

let complementary_helix (x: helix) : helix =
    List.map complement x

(对于它的价值,没有必要指定类型.OCaml将推断类型.为文档指定它们是好的风格,但如果它们很明显则可能不是.)

编辑

好吧,我想这是一个家庭作业问题,你应该使用递归来解决问题.

考虑递归的方法是你要解决一小部分问题,这会给你一个较小的问题需要解决.你将较小的问题传递给自己(在解决你的小块之前或之后).您还需要知道问题何时变得如此之小,以至于没有更多的工作要做.

在您的情况下,小部分将翻译一个核苷酸到其补体.你正在做那个半好的(你有列表,你真的只想在单核苷酸上工作).但是你没有把问题的其余部分传递给自己来递归解决.你也没有检查问题是否如此之小,无所事事.

对于列表上的函数,通过将列表拆分为头部(单个元素)和尾部(列表小一个),大约99%的时间可以使问题变小.这对你有用.

编辑2

作为列表递归的外观示例,这里有一个函数可以将列表中的所有整数相加:

let rec sum l =
    match l with
    | [] -> 0
    | head :: tail -> head + sum tail

这包含我描述的所有部分.在match既用来告诉当问题是微不足道的(当列表为空),并以列表分成头部和尾部.假设你有尾巴的总和(你可以递归地得到),答案是非常明显的.你只需要在这个总和上添加头部.你只需要问自己(几乎总是):如果我对列表的尾部有答案,我需要做些什么才能将它与头部结合起来？