3

我有一个函数规范，说明它应该评估一个变量的多项式函数。函数的系数以列表形式给出。它还接受变量的值作为实数。

例如：eval(2, [4, 3, 2, 1]) = 26 (1*x^3 + 2*x^2 + 3*x^1 + 4*x^0, 其中 x = 2)

这是python中的函数，但我不确定如何将其转换为SML。我很难找到一种在不更改函数参数的情况下将迭代值传递给它的方法。它需要保持一个真正的 * 真正的列表 -> 真正的功能。 

def eval(r, L):
    sum = 0
    for i in range(0, len(L)):
        sum = sum + L[i] * (r ** i)
    return sum
4

2 回答 2

4

用函数式语言表达和的常用方法是折叠。您可以通过在每次迭代中将总和乘以 r 来消除对索引（以及将 int 提升到另一个 int 的幂的函数）的需要：

fun eval radix lst = let
  fun f (element, sum) = sum * radix + element
in
  foldr f 0 lst
end

现在可以像这样使用该函数：

- eval 10 [1,2,3];
val it = 321 : int
于 2010-02-22T18:54:28.433 回答
1

您可以使用显式递归来遍历系数列表，对基数求幂，并对总数求和。

fun eval r =
    let fun step (power, sum) (coeff :: rest) =
                step (power * r, sum + coeff * power) rest
          | step (_, sum) nil = sum
    in step (1, 0)
    end

从结构上讲，这就像一个折叠，如果我们用一个替换它会变得更清晰。

fun eval r lst =
    let fun step (coeff, (power, sum)) = (power * r, sum + coeff * power)
        val (_, sum) = foldl step (1, 0) lst
    in sum
    end

您可以颠倒操作顺序以使用霍纳的方案，如 KennyTM 的评论中所述：这将导致 sepp2k 的答案，它需要一半的乘法，但使用更多的堆栈空间。

于 2010-02-22T19:22:30.387 回答