在 OCaml 中编写函数的问题

Question

我正在尝试编写一个函数来创建给定数字的幂列表。

一个例子：

powList(2,5) = [0, 2, 4, 8, 16, 32]

这是我已经编写的代码：

    let rec powList (x,n) =
  if n = 0 then []
  else  (let a = let rec power (x, n) =
        if n = 0 then 1 
        else  x * power (x, n-1) in a) ::: powList(x, n-1);;

这就是我遇到的问题

    Line 5, characters 31-32:
5 |         else  x * power (x, n-1) in a) ::: powList(x, n-1);;
                                   ^
Error: Syntax error: operator expected.

我才刚刚开始使用 OCaml 编写代码，因此我将不胜感激任何帮助

Answer 1

一些通用的评论：

不要在递归函数内部定义（递归）函数。提前定义辅助函数将使您的代码更具可读性，并减少出现语法错误的空间。例如，将 power 的定义提升到 powList 之外会给你

let rec power x n =
  if n = 0 then 1
  else x * power x (n-1)
  
let rec powList (x,n) =
  if n = 0 then []
  else  ( power ??? :: powList(x, n-1));;

其次，向列表添加元素是使用 :: 而不是 :::
第三，函数通常在惯用的 OCaml 代码中被柯里化

let rec powList x n = ...

而不是

let rec powList (x,n)

因为这为组合开辟了更多途径。

第四，您的实现效率低下，因为它在每一步都重新计算 x^n 而没有快速求幂。因此，您的代码最终会计算 n * (n+1)/2 次乘法。使用快速取幂会将乘法次数减少到 O(n log n)。然而，使用 x^(n-1) 计算 x 的更简单版本仅产生 n 乘法：

let pow_list x n =
 let rec pow_list x_power_n n =
   if n = 0 then ...
   else ...
 in
 pow_list ...

在 OCaml 中编写函数的问题

The problem with writing a function in OCaml

ocaml

syntax-error