Admin
1
Why is it that in some functions when I use modules like List.filter it does not return an error: stack overflow
but when I use
let rec filter p l =
match l with
| [] -> []
| hd::tl -> if p hd then hd::(filter p l) else filter p l
which has the same functions as List.filter it produces the stack overflow error
Your filter function calls itself recursively with the same list l:
... then hd::(filter p l) else filter p l
^^^^^^^^^^^^ ^^^^^^^^^^
This means you never converge towards a solution, you are recursing infinitely.
Reaching Stack Overflow on small inputs is a symptom of such problems. Likewise, when you write a tail-recursive function you may have non-terminating loops, which is another way to identify when the program is incorrect (some programs are infinite loop on purpose).
In your case you need to use tl, the remaining elements from the list. Having something that shrinks at each step of recursion is important if you expect the function to terminate.
