> I'm just starting to play with OCaml and I wrote the following function:
> 
> let rec is_sorted lst =
>     match lst with
>        [] -> true
>     | [elt] -> true
>     | a :: b :: tail -> a<b & is_sorted(b :: tail)
> 
> 
> I'm wondering whether the b :: tail actually allocates memory or is 
> the compiler smarter than that?

Yes it does, since you explicitely asked for it.

>  What's the best way to avoid this? 

Name the input sub-pattern (b :: tail) and use it in place of an
explicit call to "::" :

let rec is_sorted lst =
  match lst with
  | [] -> true
  | [elt] -> true
  | a :: (b :: tail as first_tail) -> a < b && is_sorted first_tail

> If I rewrite to match instead with "a :: tail" (and then later pull 
> that apart into b :: more_tail) am I guaranteed that tail is 
> non-empty because of the prior [elt] case?

Yes and no. If you write:

  match lst with
  | [] -> true
  | [elt] -> true
  | a :: tail -> ...

then you are guaranted that tail cannot be empty (this is witnessed by
the compiler that cheks it and does not emit any ``partial match''
warning).

However, if you further match the tail pattern in the right hand part
of the clause, the compiler ``forgets'' this fact and performs a new
exhaustivity check from scratch:

let rec is_sorted lst =
  match lst with
  | [] -> true
  | [elt] -> true
  | a :: tail ->
     begin match tail with
     | b :: t -> a < b && is_sorted tail
     end;;
Warning: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
[]
val is_sorted : 'a list -> bool = <fun>

Anyway, I would suggest a simpler solution to implement this function:

let rec is_sorted = function
  | a :: (b :: _ as t) -> a < b && is_sorted t
  | _ -> true;;

Best regards,

PS: If you allow duplicated elements in lists you should use <=
instead of < ...

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/