OCaml:带整型列表的函数

Question

我试图在OCaml中编写一个简单的函数

let rec pell (i: int) =
(if i <= 2 then i (*if given n is less tahn 2 then return 2, else return previous n-1 th term and n-2 nd term recursively*)
else if i>2 then
2 * pell i - 1 + pell i - 2
else failwith "unimplemented" (*else fail with unimplemented message*)
);;

为

之前的pell函数写一个无限精度的版本

pell2 0 = []
pell2 1 = [1]
pell2 7 = [9; 6; 1]
pell2 50 = [2; 2; 5; 3; 5; 1; 4; 2; 9; 2; 4; 6; 2; 5; 7; 6; 6; 8; 4]

我写了下面的代码:

let rec pell2 i =
(if i <= 2 then
[] -> i;
else if i=0 then [];
else if i>2 then                                (*finding pell number and using sum function to 
output list with infinite precision...*)
[] -> pell2 i-1 + pell2 i-2;
else failwith "unimplemented"
);;

仍然有一些语法错误。有人能帮我一下吗?

Answer 1

if i <= 2 then
[] -> i

在这样的代码片段中，->是无效的。它看起来像你可能混合模式匹配与match ... with ...和if/else up。

同样，您首先检查i是否小于或等于2，但随后您有else要测试i是否等于零。第一次检查意味着第二次检查永远不会发生。

Answer 2

首先，让我们看一下pell2输出的示例。我们看到pell2只有一个整数形参，并返回一个整数列表。因此，我们知道我们想要创建的函数具有以下类型签名:

pell2: int -> int list

修复(部分但不是全部)语法错误并试图维护您的逻辑，

let rec pell2 i =
if i=0 then []
else if i <= 2 then i
else if i>2 then pell2 i-1 + pell2 i-2

请注意，我删除了每个表达式末尾的分号，因为OCaml在其语法中使用分号是专门用于处理求值为单位()的表达式。请参阅ivg对此的精彩解释。这段代码的主要缺陷是它没有进行类型检查。可以看到，我们有条件地返回一个列表，否则返回一个int。注意上面我们是如何定义pell2应该返回一个int list的。因此，我们可以通过在列表中包装int结果来开始修复这个问题:

let rec pell2 n = 
if n = 0 then []
else if n <= 2 then [n]
else ... something that will return the Pell number as a list ...

正如您已经写过的，可以使用对pell2函数的递归调用来编写else分支。但是，我们不能像前面那样编写它，因为pell2的计算结果是一个列表，而二进制运算符+只能处理两个整数。所以，我们必须定义我们自己的求和表的方法。调用此sum_lists，我们留下以下代码:现在可以完全定义函数pell2:

let rec pell2 n =
if n = 0 then []
else if n <= 2 then [n]
else (* Pell(n) = (2 * Pell(n-1)) + Pell(n-2) *)
let half_of_first_term = pell2 n-1 in
let first_term = sum_lists half_of_first_term half_of_first_term in
let second_term = pell2 n-2 in
sum_lists first_term second_term

所以，剩下的就是定义sum_lists，这样我们就可以正确地将两个格式与pell2返回类型相同的列表相加。sum_lists的签名是

sum_lists: int list -> int list -> int list

我将给出一个基本的实现大纲，但剩下的部分留给你自己去想，因为这是分配问题的主要症结。

let sum_lists lst1 lst2 =
let rec sum_lists_helper lst1 lst2 carry =  
match lst1, lst2 with
| [], [] -> if carry = 1 then [1] else []
| h::t, []
| [], h::t -> ...
| h1::t1, h2::t2 -> ...
in
sum_lists_helper lst1 lst2 0