SML 中的霍纳算法？ [关闭]

我正在尝试实施霍纳算法 http://en.wikipedia.org/wiki/Horner%27s_algorithm in SML.

fun horner(lst1:real list,x:real) = 
  let
    val i = ref 1
    val result = ref (List.last(lst1))
    in
      if (lst1) = ([]:real list) then 0.0 
      else
        while (!i <= length(lst1)-1) do
          (result:=!result*x+List.nth(lst1,length(lst1)-(!i)-1);
          i := !i+1);
          !result
      end;

采用 a{n}（x^n 的系数）作为其初始结果，然后使用霍纳计算多项式。

计算结果为 ((a{n}*x+a{n-1})*x+a{n-2})..该列表包含多项式的系数。 问题是“if lst1 = []....else”部分。 仅使用 while 循环即可使程序运行良好。 但我想不出这部分有什么问题。

您尝试编写一些看起来非常命令式的代码，坦率地说，这有点混乱。如果您尝试像 Java 一样编写 SML 代码，那么，这会很糟糕。

让我们以更实用的风格重做它，而不是尝试修复原始代码。首先，模式匹配。在您的代码中，您使用if-then-else表达式来检查列表是否为空。相反，我们将使用模式匹配：

fun horner ([]   , x) = 0.0
  | horner (n::ns, x) = ...

这有两个好处。首先，它为我们拆分了列表 - 我们现在可以使用n引用列表中的第一项，并且ns来参考其余的。其次，它更具可读性。

现在我们需要实际的数学。现在，霍纳的方法使用一个变量，您将其称为result在您的代码中，积累答案。然而，我们主要使用函数式语言进行编码，并避免ref那就太好了。相反，我们将向该函数添加一个额外的参数。

fun horner ([]   , x, acc) = acc
  | horner (n::ns, x, acc) = ...

当然，我们希望该函数仅使用两个参数即可使用，因此我们将数学放入辅助函数中，并使实际函数调用该辅助函数：

fun horner' ([]   , x, acc) = acc
  | horner' (n::ns, x, acc) = ...

fun horner (xs, x) = horner' (xs, x, 0.0)

这是函数式编程中相当常见的模式，SML 有隐藏辅助函数的工具，这样我们就不会弄乱全局命名空间。例如，我们可以将辅助函数放入let-表达：

fun horner (xs, x) = let
                       fun horner' ([]   , x, acc) = acc
                         | horner' (n::ns, x, acc) = ...
                     in
                       horner' (xs, x, 0.0)
                     end

最后，我们添加递归调用horner'.

fun horner (xs, x) = let
                       fun horner' ([]   , x, acc) = acc
                         | horner' (n::ns, x, acc) = horner' (ns, x, n + x * acc)
                     in
                       horner' (xs, x, 0.0)
                     end

这是当我们调用时会发生什么horner功能：

horner ([3.0, 2.0, 4.0], 2.0) ~> horner' ([3.0, 2.0, 4.0], 2.0, 0.0)
                              ~> horner' ([2.0, 4.0]     , 2.0, 3.0 + 2.0 * 0.0)
                              ~> horner' ([2.0, 4.0]     , 2.0, 3.0)
                              ~> horner' ([4.0]          , 2.0, 2.0 + 2.0 * 3.0)
                              ~> horner' ([4.0]          , 2.0, 8.0)
                              ~> horner' ([]             , 2.0, 4.0 + 2.0 * 8.0)
                              ~> horner' ([]             , 2.0, 20.0)
                              ~> 20.0