Sort List in OCaml

Question

Here is the sort code for any 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 get 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 someone please help me understand the problem here? I did not find head or tail to predefine anywhere and in code

Answer 1

Your code seems to be 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 type of list is defined as:

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

and that you match your lst list.

Answer 3

Symbol "|" is a symbol of a horizontal line, it is not a symbol l, but a symbol → minus and a large symbol. I think you copied and pasted the code segment into the Inria website. Check and rewrite special characters. I tested it and it works well.

Answer 4

No need to define the head and tail. They are matched against the "list" that you give.