Tail recursion in SML does not present any output

Question

Following my previous post here , I tried to do what was suggested and convert the code into a Tail-recursion method with let .

The original code - which does not work (due to using val inside if condition) :

fun func() = 

val decimal = 0 (* the final result *)
val multiple = 0 (* keeps track of multiples, eg. In XXV, X would be a multiple *)
val current = 0 (* the digit currently being processed *)
val top = 0   (* value of the last element in the list *)
val last_add = 0 (* the last digit that wasn't a multiple, or subtraction operation *)
val last_sub = 0
val problem = 0 (* if value is 1 then there is a problem with the input *)
val myList = [1,2,3,4,5] (* the list has more values *)

while (myList <> [])    (* run while the list is not empty *)

    val current = tl(myList) (* grab the last element from the list *)
    val myList = tl(myList) (* remove the last element from the list *)
    val top = tl(myList) (* grab the value at the end of the list *)
    if ( myList <> []) andalso (current > top))
       then      

                val decimal = decimal + current - top
                val last_sub = top;
                val myList = tl(myList)
       else     
           if ( (myList = []) andalso (current = top))
              then val decimal = decimal + current
                   val multiple = multiple + 1
              else
                  if (last_sub = current)
                     then val problem = 1

                     else
                          val decimal = decimal + current
                          val multiple = 0
                          val last_add = current

And the code as a tail-recursion method :

fun calc [] = 0
    |calc [x] = x
    |calc (head::tail) = 
       let 
          val decimal = 0
          val multiple = 0
          val current = 0
          val top = 0  
          val last_add = 0
          val last_sub = 0
          val problem = 0  
          val doNothing = 0
       in      

          let
              val current = hd(rev(head::tail))  (* grab the last element *) 
              val head::tail = rev(tl(rev(head::tail)))  (* POP action - remove the last element from the list *)
              val top = hd(rev(head::tail))      (* grab the new last element after removing *)
              in 
                if (current > top) then 
                    let 
                          val decimal = decimal + current - top
                          val last_sub = top 
                          val head::tail = rev(tl(rev(head::tail)))  (* POP action - remove the last element from the list *)
                    in
                    calc(head::tail)
                    end
                else
                 if ( (head::tail = []) andalso (current = top))
                   then let 
                          val decimal = decimal + current
                          val multiple = multiple + 1
                        in 
                          calc(head::tail)
                        end
                 else 
                     if (last_sub <> current)
                       then let 
                               val decimal = decimal + current
                               val multiple = 0
                               val last_add = current
                            in 
                               calc(head::tail)
                            end
                     else
                        (* do nothing *)    
                        val doNothing = 0
               end      

       end; 

However , when I try to enter :

calc([0,100,20,30,4,50]);

I get :

uncaught exception Bind [nonexhaustive binding failure]
  raised at: stdIn:216.13-216.50

I know the code is very hard to read and pretty long , but it would be greatly appreciated if someone could explain to me how to fix it , or help me find the reason for this output .

Thanks

Answer 1

You have a few issues with your code.

First of all, you can use last to grab the last element of a list. See the List documentation for more info. But unless you have a really good reason to do so, it's easier and much more efficient to simply start from the beginning of the list and pop elements off the beginning as you recurse. You already have the first element bound to head in your code using pattern matching.

Secondly, unless you use refs (which you probably don't want to do) there are no variables in Standard ML, only values. What this means is that if you want to carry state between invocations, any accumulators need to be parameters of your function. Using a helper function to initialize accumulators is a common pattern.

Third, instead of comparing a list to [] to test if it's empty, use the null function. Trust me on this. You'll get warnings using = because of subtle type inference issues. Better yet, use a pattern match on your function's parameters or use a case statement. Pattern matching allows the compiler to tell you whether you've handled all possible cases.

Fourth, SML typically uses camelCase, not snake_case, for variable names. This is more stylistic, but as you write more code and collaborate, you're going to want to fit with the conventions.

Fifth, when you do recursion on a list, don't try to look at multiple values in the list. This complicates things. Treat it as a head element and tail list, and everything will become much simpler. In my code, instead of keeping current in the list, I did this by splitting it out into a separate parameter. Have a base case where you simply return the answer from one of your accumulators, and a recursive case where you recurse with updated accumulator values and a single value popped from your list. This eliminates the problem scenario.

I'm not sure if this logic is correct since I don't know what you're trying to calculate, but check out this code which illustrates some of the things I talked about.

(* This is the helper function which takes accumulators as
   parameters. You shouldn't call this directly. *)
fun calc' decimal _ _ _ _ [] =
    (* We processed everything in the list.  Just return the accumulator. *)
    decimal
  | calc' decimal multiple lastAdd lastSub current (top::tail) =
    (* This case is for when there are 1 or more elements in the list. *)
    if current > top then
        calc' (decimal + current - top) multiple lastAdd top top tail
    else if current = top then
        calc' (decimal + current) (multiple + 1) lastAdd lastSub top tail
    else
        calc' (decimal + current) 0 current lastSub top tail

(* This is the function you should call. *)
fun calc [] = 0
  | calc [_] = 0 (* Given a single-element list. *)
  | calc (x::xs) =
    (* Apply the helper with correct initial values. *)
    calc' 0 0 0 0 x xs

In a functional language, instead of assigning to a variable when you want to change it, simply recurse and specify the new value for the correct parameter. This is how you write a "loop" in a functional language using recursion. As long as you only use tail-recursion, it will be just as efficient as a while loop in your favorite imperative language.