functional-programming - 在 SML 中创建迭代函数

Question

我已经被这个问题困扰了一段时间，想不出如何解决它。

考虑以下函数 f : N → N 。

f(0) = 2, f(1) = 0, f(2) = 3,

对于 n≥3，f(n) = 3f(n-3) + 2f(n-2) - f(n-1)。

定义 f 的迭代版本。

我知道我的解决方案应该是这样的

fun myFun 0 = 2
|   myFun 1 = 0
|   myFun 2 = 3
|   myFun n = 
       let
        (* code *)
       in
         funHelp(3,2,0,n)
       end ;

我知道迭代函数只假设使用一个递归调用，而让参数完成所有工作。不过，我不知道如何解决这个问题！任何帮助将非常感激！

Answer 1

我认为这是家庭作业，所以我只给你一个部分解决方案：

fun f n =
    let
      fun iter(0, n0, n1, n2) = n0
        | iter(1, n0, n1, n2) = n1
        | iter(2, n0, n1, n2) = n2
        | iter(n, n0, n1, n2) = iter(n - 1, n1, n2, ???)
    in
      iter(n, 2, 0, 3)
    end

填写？？？不应该太难。

Answer 2

fun funHelp 0 = (2,0,3)
  | funHelp n = let val (x,y,z) = funHelp n - 1
                in
                  (y,z,(3 * x) + (2 * y) - z)
                end

fun myFun n = let val (x,_,_) = funHelp n
              in
                x
              end

这应该做你似乎想要的，如果有点混乱的话。