CODEWITHSUNDEEP
ocaml
user13648242
user13648242

Reputation:

Ocaml Stackoverflow

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

Upvotes: 2

Views: 267

Answers (1)

coredump
coredump

Reputation: 38809

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.

Upvotes: 1

Related Questions