I am very new to Ocaml, although I suspect that you will be able to work this out from the question that I am about to ask.
I am trying to write a recurring function to check if an item is present in a list. I have seen a way to do this that works, but I am confused as to why my solution gives the result of ‘true’, even when the item is not present in the list.
let rec belongs lst x =
match lst with
[] -> false
| x::t -> true
| h::tail -> belongs tail x;;
This function correctly returns false if I send it an empty list, but it also always returns true if the list is not empty (along with any random ‘x’) regardless of whether or not x is present in the list.
My hunch is that it is not identifying the ‘x’ in ‘x::t’ with the ‘x’ that is one of the two inputs to the function, but I am puzzled as to why that is the case. I am still new enough to Ocaml to realise that I could be completely wrong in this guess as to why the code is not working properly …
Anyway, any corrections or help much appreciated.
let rec belongs lst x =
match lst with
| [] -> false
| h::_ when h = x -> true
| _::tail -> belongs tail x
or alternatively
let rec belongs lst x =
match lst with
| [] -> false
| h::tail -> h = x || belongs tail x
or alternatively
let belongs lst x = List.mem x lst
In patterns you name values according to some structure and thus introduce new names. You simply introduced a new x.
Furthermore, since they introduce new names, matching x::t or h::tail is the exact same thing. Thus the last case will never be reached and I am confident the compiler warned you.
Thank you for all those suggestions. I tried it in the online Ocaml (https://try.ocamlpro.com/) and it did not give a warning, but perhaps the online version lacks some features.
If I have understood it correctly, I really like the last line of your second suggestion - what a neat use of ‘OR’. Does Ocaml return true immediately if ‘h=x’ is true, thus preventing unnecessary recursion in the second clause?
OCaml will not recurse if the first condition returns true. This behaviour is specific to the boolean || and && operator and is coined as short-circuiting. It is present in most if not all common languages.
FWIW I checked the interpreter you linked to and although it does print compilation errors, warnings are indeed missing.
I must say this is a bit disappointing. One of the language features that as a newcomer striked me as tremendously helpful at the time was the pattern exhaustiveness and shadowing warnings…
I used the online version as I am at work - I will try properly at home, where I have Ocaml installed. I am grateful for the existence of a free online version, but I take your point and will try to do more of my learning with an installed version.
Yes, that online interpreter was more thought of as a demonstration tool than a real thing. We are actually working on a way better tool to replace it.
utop (Universal toplevel for OCaml) actually shows the warning, and I would suggest using it to learn OCaml and when practicing examples. See: https://opam.ocaml.org/blog/about-utop/
utop # let rec belongs lst x =
match lst with
[] -> false
| x::t -> true
| h::tail -> belongs tail x
;;
Line 5, characters 4-11:
Warning 11: this match case is unused.
val belongs : 'a list -> 'b -> bool = <fun>
utop #
There’s also another thing which might ought to be noted. In many languages, defining a variable “x” in a scope where “x” is already defined, yields a warning/error. E.g. in Golang (IIRC). In languages derived from the functional lineage (like Ocaml) it does not, because these languages -encourage- programmers to do this very thing. So for instance, instead of
int x = 1 ;
....
x := 2;
....
x := arglebargle ....
we get
let x = 1 in
....
let x = 2 in
.....
let x = arglebargle ... in
....
Just an FYI. It’s intended to encourage the reuse of variable-names when they stand for “redefinition” (in the sense of flow-analysis, maybe) of the value of the identifier.