Need hints (not code) converting this recursive function to tail recursive?

Question

I have this function that takes a list of lists of strings and a string and then return a list of all the elements in each list that contains the string passed but without the string passed.

myfilter([["a","b"],["c","d"],["e","a","x"]], "a") -> ["b","e","x"]

fun myfilter(list : string list list, s : string) =
case list of
    [] =>  []
   |xs::xs' => case all_except_option(s, xs) of (* helper function that does it for a string and a list of strings *)
                   NONE => []
                  |SOME n => if n = xs
                             then myfilter(xs',s)
                             else n@myfilter(xs',s)

Now this is as you can see is a recursive function and I want to convert it to a tail recursive function. I am familiar with the examples of tail recursion but I am failing to see how I can do it in the function above

You're not supposed to get "hints", either, as specified in your assignment. Rewatch the last three lectures instead. — cbrandolino
– cbrandolino, Commented Jan 31, 2013 at 13:11
Have you seen the discussion board. It's full of them . Came here because there was not much help over there for this problem and I did not want to post my code there — awm
– awm, Commented Jan 31, 2013 at 15:47

Tayacan · Accepted Answer · 2013-01-31 09:38:10Z

5

When you think tail recursive, the next thing you think should be "accumulator".

The reason a function is not tail recursive is that it has to call itself to obtain some result, and then do something with that result. If we can move that calculation into the recursive call, then it's tail recursive.

In this case, the calculation you're making is that you're putting two lists together. So the solution would be a function declared inside a let ... in ... end, that takes a third parameter - an accumulator. Then you can add items to the accumulator as you go.

A good example is a tail-recursive factorial function. Here's the normal factorial function:

fun fact 0 = 1
  | fact x = x * fact (x-1)

To make it tail-recursive, we define a local function which takes an accumulator, and do the multiplication there.

fun fact x =
let
  fun fact' 0 acc = acc
    | fact' x acc = fact (x-1) (x*acc)
in
  fact' x 1
end

We use 1 as the starting value for the accumulator, because multiplying with 1 has no effect.

Okay, so other than that, there is a little thing you can do to improve your code. I've noticed a lot of people here that do this:

fun foo xs =
case xs of
    []      => ...
  | (x::xs) => ...

Where it would be much nicer to just do:

fun foo []      = ...
  | foo (x::xs) = ...

answered Jan 31, 2013 at 9:38

Tayacan

1,82611 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

awm Over a year ago

Thanks a lot. I ll give it another try.

awm Over a year ago

I ended up with a solution that works, but I am not sure how to verify it is tail recursive. Is there a way?

Tayacan Over a year ago

Well... Look at your recursive call. Is the result used in any computation? If it is, it's not tail recursive.

Collectives™ on Stack Overflow

Need hints (not code) converting this recursive function to tail recursive?

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related