CODEWITHSUNDEEP
recursionsmltail-recursion
DimitrisChousiadas
DimitrisChousiadas

Reputation: 133

How to convert a recursive function into a tail recursive one in SML?

I am trying to write a function in SML that is going to return a subsequence of the elements of a list, as well as a sequence of the rest of the elements of the list. So, my function is

fun subseq (left,right,0) = (left,right) |
    subseq (left,h::t,len) =
       let
          val (left,right) = subseq ([],t,len-1)
       in
          (h::left,right)
       end;

fun subseqMain (mainList, length) = subseq ([],mainList,length);

My question is how to make this function more efficient, by converting it to a tail recursive one, without using the @ operator.

Thank you for your time!

Upvotes: 1

Views: 953

Answers (1)

Matt
Matt

Reputation: 4049

The easiest way to do this is to use rev. Basically, the idea is to cons onto left in each iteration. Your left subsequence will then be in reverse order, which is where rev comes in. It is unfortunate that you have to make two passes over the subsequence, but there really isn't anything else that you can do that will be much faster. The performance gain that you will achieve is dependent on what compiler that you are using. SML/NJ performs a CPS transformation, so non-tail calls incur a small amount of heap allocation as opposed to stack allocation, so you pay some GC overhead. You can see throughout the SML/NJ Basis that they do this sort of thing in a few places, for example, the definition of partition is 

fun partition pred l = let
      fun loop ([],trueList,falseList) = (rev trueList, rev falseList)
        | loop (h::t,trueList,falseList) = 
            if pred h then loop(t, h::trueList, falseList)
            else loop(t, trueList, h::falseList)
      in loop (l,[],[]) end

Your other option is to manually transform this into Continuation Passing Style (CPS), where you basically wrap the "rest of the computation" up in a function, which we call the continuation. When a function finishes, it simply passes its result off to the incoming continuation. Explaining CPS in its entirety is probably beyond the scope of this answer, so I would suggest doing some Googling to get a real grasp on it. The partition example might look something like this:

fun partition pred l = let
    fun loop([], k) = k([], [])
       |loop(h::t, k) = loop(t, fn (tr, fl) => if pred h then k(h::tr, fl) else k(tr, h::fl))
    in loop(l, fn res => res) end

That said, if you are not going to convert to tail recursion, there is a more straightforward way of implementing what you have:

fun subseq(l, 0) = ([], l)
   |subseq(h::t, i) = 
      let val (l, r) = subseq(t, i-1)
      in (h::l, r) end
   |subseq([], i) = raise Subscript

Upvotes: 2

Related Questions