CODEWITHSUNDEEP
functional-programmingsmlsmlnj
user2796815
user2796815

Reputation: 465

Creating an iterative function in SML

I've been stuck on this problem for a while now, and can't think of how to solve it.

Consider the following function f : N → N .

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

f(n) = 3f(n-3) + 2f(n-2) - f(n-1) for n≥3.

Define an iterative version of f.

I know my solution should look something like this

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

I know iterative functions are only suppose to use one recursive call, while letting the arguments do all the work. I can't figure out how to do it with this problem, though! Any help would be much appreciated!

Upvotes: 2

Views: 351

Answers (2)

Andreas Rossberg
Andreas Rossberg

Reputation: 36098

I assume this is homework, so I just give you a partial solution:

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

Filling in the ??? shouldn't be too hard.

Upvotes: 2

qaphla
qaphla

Reputation: 4733

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

This should do what you seem to want, if a bit messily.

Upvotes: 0

Related Questions