从命令式编程到函数式编程的转换 [从Python到Standard ML]

Question

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

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

这是Python中的函数，但我不知道如何将其转换为SML。我遇到了麻烦，找不到一种在不改变函数参数的情况下传递迭代值的方法。它需要保持一个real * real list -> real函数的形式。

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

- efritz

---

尽量不要将函数命名为“eval”。已经有一个内置的 eval 函数(http://docs.python.org/library/functions.html#eval) 执行完全不同的操作。 - kennytm

名称已经在规范中了。Python 代码仅供参考。至少，在 SML 中 eval 应该是名称。 - efritz

最好使用霍纳方案（http://en.wikipedia.org/wiki/Horner_scheme）来求解多项式。 - kennytm

Answer 1

在函数式编程语言中表达总和的常规方法是使用fold。您可以通过在每次迭代中将总和乘以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

- sepp2k

---

这个代码可以运行，但是任务明确要求使用模式匹配的解决方案，所以我猜测应该手动运行算法，而不是使用fold/foldl或foldr。 - efritz

Answer 2

你可以使用显式递归来遍历系数列表，对基数进行指数运算，并总和求和。

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

您可以通过使用Horner方案来颠倒操作顺序，正如KennyTM的评论中所提到的那样：这将导致sepp2k的答案，它需要一半的乘法，但使用更多的堆栈空间。

- ephemient

---

这个代码可以运行，但是任务明确要求使用模式匹配的解决方案，所以我猜测应该手动运行算法，而不是使用fold/foldl或foldr。 - efritz