Ocaml Pattern Matching Qualms

Question

I'm having a bit of a problem with regards to pattern matching in Ocaml.

Basically, I need to write a function named reversed that accepts a list and checks whether or not it is in reversed order.

So far:

let rec reversed (x:int list):bool =
   match x with
   | [] -> true
   | y::z::tl -> if y < z then false else reversed tl;
   | y::[] -> true;;

It works! (to my surprise actually :P) But there is a flaw I can see, that is if there is no more tl, it would not match. Testing this returns true:

  reversed [5;4;3;1;2];;

Which is perfectly understandable since there's no more tail and it simply matches to y::[]

How would I fix this?

PS: This is my first day with Ocaml. Sorry if the question is very easy :D

PPS: I am purposely only using Core. (no modules)

PPPS: I understand the case if I'm doing something fundamentally wrong, please do point it out.

Answer 1

The problem in your function is here :

| y::z::tl -> if y < z then false else reversed tl;

Let's look at your list : [5;4;3;1;2]

It is decomposed this way :

| 5::4::[3;1;2]

And you compare 5 and 4, and then call reverted with [3;2;1]. Wich means that the comparaison between 4 and 3 is not done ! (you can try with a list like [5;4;99;98;97], it is the unexpected result that you have).

What you should do is test on z, and then call reverted with the rest of the list. But if you try something like :

| y::z::_ -> if y < z then false else reversed z;

The compilers yells at you, because z is an int (and not an int list anymore). To solve this, you can "reconstruct" the list by adding z in front of tl :

| y::z::tl -> if y < z then false else reversed (z::tl)

Or name the list after y (which contains z) while still extracting z :

| y::(z::_ as tl) -> if y < z then false else reversed tl

As for your guess about the problem, I understand your logic but actually it does not work that way. [] can be "named" in your decomposition, just as if it was a regular node.

Look at this example, a (bad) function who tests if the end of the list is reached :

let is_end l = match l with | a -> false | [] -> true;;

If you try to put that in your interpreter, you should get the following message : Warning 11: this match case is unused.

That's because [] is already caught in the first match case. You can try with is_end [], it returns false.

The correct way to handle this is how you did it in your code :

let is_end l = match l with | x::_ -> false | [] -> true;;

Answer 2

Your program logic is wrong. You want to check if the list is reversed (decreasing?). But your program fails on input

[5;3;4;2;1]

telling you that it is reversed/decreasing. This is because you drop the 3 too early. Your middle clause should be:

   | y::z::tl -> if y < z then false else reversed (z::tl);

Answer 3

You should use | y::z::tl -> if y < z then false else reversed (z::tl).

if y > z, you shouldn't drop z from the next round of list because z has not been compared to the next item yet.

Also you don't need ; in that line.

the correct code is

let rec reversed = function
  | [] -> true
  | hd::[] -> true
  | hd1::hd2::tl ->
    if hd1 < hd2 then false
    else reversed (hd2::tl)

Answer 4

Here is another way to write it using some other concepts like pattern guards and wild cards:

let rec reversed = function
  | [] | [_] -> true
  | hd1::hd2::_ when hd1 < hd2 -> false
  | _::tl -> reversed tl;;

This way there is one case for true, one for false, and one recursive.