Sorting a list in OCaml

Question

Hi All,

Here is the code on sorting any given list:

let rec sort lst =
   match lst with
     [] -> []
   | head :: tail -> insert head (sort tail)
 and insert elt lst =
   match lst with
     [] -> [elt]
   | head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail;;

[Source: Code

However, I am getting an Unbound error:

Unbound value tail
# let rec sort lst =
   match lst with
     [] -> []
   | head :: tail -> insert head (sort tail)
 and insert elt lst =
   match lst with
     [] -> [elt]
   | head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail;;
Characters 28-29:
     | head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail;;
     ^
Error: Syntax error

Can anyone please help me understand the issue here?? I did not find head or tail to be predefined anywhere nor in the code

Answer 1

Your code seems correct, and compiles for me:

    Objective Caml version 3.11.1

# let rec sort lst = ...

val sort : 'a list -> 'a list = <fun>
val insert : 'a -> 'a list -> 'a list = <fun>

# sort [ 1 ; 3 ; 9 ; 2 ; 5 ; 4; 4; 8 ; 4 ] ;;
- : int list = [1; 2; 3; 4; 4; 4; 5; 8; 9]

Answer 2

Adding to what Pascal said, the list type is defined as:

type 'a list = [] | :: of 'a * 'a list

and that's what you are matching your list lst against.