1

I'm writing a program which remove first element which fit to predicate eg.

remove' (fun x -> x = 2) [1;3;2;4;2] => [1;3;4;2]

and the problem is: how to write it with foward recursion? Is it possible? With tail recursion it is not a problem. I just add next elements to acc if they are not fit to predicate.

I was thinking about

List.fold_right,

but maybe is there different way to do this?

botero
  • 598
  • 2
  • 11
  • 23
Ojmeny
  • 1,286
  • 2
  • 13
  • 25

2 Answers2

2

There is no such thing as "forward recursion". Tail recursion defines a special kind of recursion, that occurs in a tail position. When you want to refer to a recursion that is not in a tail position, you call it "non tail recursive"

In the code you've specified there is no recursion at all. So, I would suggest you first of all to try to write remove_if function and try to figure out whether it is tail or non-tail.

Update

I usually try no to solve homework for others, but at this case I will give a little kick start, by providing you with the most common definition of remove_if function:

 let rec remove matches = function
    | [] -> []
    | x :: xs when matches x -> remove matches xs
    | x :: xs -> x :: remove matches xs

There are two occurrences of recursion in this function:

| x :: xs when matches x -> remove matches xs
                            ^^^^^^^^^^^^^^^^^
                            last expression - 
                            tail recursion

| x :: xs -> x :: remove matches xs
                  ^^^^^^^^^^^^^^^^^
                  not the last - 
                  non tail recursive

So, last case needs some clarification: before the x can be prepended to the result of remove matches xs the latter expression needs to be evaluated. That means that computer needs to store x somewhere, to wait until remove matches xs is evaluatd.

So, no the fun part, you have a non-tail recursive version. Now, try to implement it tail recursively. Have fun!

ivg
  • 34,431
  • 2
  • 35
  • 63
  • I have read "foward recursion" on stackoverflow. Sorry if i'm getting wrong. The point is, that I have to write 'non tail recursive' and 'tail recursive' remove function. As I said, algorithm of 'non tail recursive' is problem for me. I have no idea how to make it works. – Ojmeny Apr 06 '15 at 23:25
  • actually, I think that you should first try to write any implementation of the `remove_if` function. (The usual definition is actually non tail recursive, so it is harder to write tail recursive). And, as far as I understand, you can't use library functions to write `remove_if`, you need to use recursion – ivg Apr 06 '15 at 23:27
  • ok, since you're lost in terminology, I showed you an example of trivial _non_ tail recursive implementation. – ivg Apr 06 '15 at 23:45
  • 1
    A fold is sufficient, it's just `let remove_if p l = List.fold_right (fun e a -> if p e then a else e::a) l []`. Of course this is not the remove-only-one operation that the OP asks for. (That's also possible with `fold_right`, but ugly.) – gsg Apr 07 '15 at 04:15
  • But I'm little confused. I thought that recursion is calling method by itself and tail-recursion is when we are using acc to store results. According to http://stackoverflow.com/questions/3042954/tail-recursion-vs-forward-recursion?rq=1 Anyway, thanks a lot! – Ojmeny Apr 07 '15 at 09:36
  • 1
    using accumulator is one particular method of achieving tail-recursion, the are other, e.g., continuation passing. – ivg Apr 07 '15 at 10:43
  • I add answer. ivg's solution was great, but it removes all occurrences of element in list. I had remove only first one. – Ojmeny Apr 07 '15 at 16:54
0

ivg solution helps me a lot, but I needed to upgrade it a little. My answer is:

 let remove' p xs =
   let rec remove_guard p xs g =
      match xs with 
        [] -> []
      | hd::tl -> if (p hd && g = 1) then remove_guard p tl 0 
                  else  hd::remove_guard p tl g
 in remove_guard p xs 1

Maybe not the best, but it removes only one element.

Thanks guys for help. I really appreciate it.

Ojmeny
  • 1,286
  • 2
  • 13
  • 25
  • 1
    Not bad, but it can be done better, instead of continuing to recurse after the first match with guard flag (btw, there is a `bool` type for this), you can just choose not to recurse at all, as the result is already ready – ivg Apr 07 '15 at 17:11
  • You have right. You are my hero! :D Thanks again! It is not only about homework, but I really like functional programming (I'm programming in Python, which has poor functional, but still programming.) and it helps me to develop my skills. – Ojmeny Apr 07 '15 at 22:22