代码之家 › 专栏 › 技术社区 › efritz

从命令式编程到函数式编程的转换[python到标准ML]

sml functional-programming parameters recursion python

efritz · 技术社区 · 14 年前

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

例如: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

2 回复 | 直到 14 年前

sepp2k 14 年前

用函数语言表示和的常用方法是折叠。您可以通过在每次迭代中将和与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

ephemient 14 年前

可以使用显式递归遍历系数列表,对基数进行指数化,然后求和。

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的评论所述,您可以颠倒使用Horner方案的操作顺序:这将导致SEPP2K的答案,它需要一半的乘法,但使用更多的堆栈空间。

推荐文章

July · 如何定义数字间隔,然后四舍五入

1 年前

Community wiki · 对象名称前的单下划线和双下划线的含义是什么?

1 年前