Making a custom user defined List type

Learning
1

For the sake of learning, I wanted to define a list. I tried:

type ‘a list = [ ] | (::) of ‘a * ‘a list

but the top level interpreter got mad at me:


# type ���a list = [ ] | (::) of ‘a * ‘a list;;
Alert deprecated: ISO-Latin1 characters in identifiers
Alert deprecated: ISO-Latin1 characters in identifiers
Alert deprecated: ISO-Latin1 characters in identifiers
Error: Illegal character (\128)
# Alert deprecated: ISO-Latin1 characters in identifiers
Alert deprecated: ISO-Latin1 characters in identifiers
Alert deprecated: ISO-Latin1 characters in identifiers
Error: Illegal character (\128)      ^CInterrupted.

why? How does one define a custom list?

2 
(* type def *)
type 'a list =
  | Nil
  | Cons of 'a * ('a list)

(* pattern matching on your type *)
let rec list_length l =
  match l with
  | Nil -> 0
  | Cons (_, s) -> 1 + list_length s

let _ =
  (* defining a value of your type *)
  let l = Cons (1, Cons (2, Cons (3, Nil))) in
  print_int (list_length l)
3

Your code example has curly quotes. Curly quotes are not valid OCaml syntax. Maybe you typed it in some editor which turns straight quotes into curly quotes? It will work if you use straight quotes. E.g.

module MyList = struct
  type 'a list = [ ] | (::) of 'a * 'a list
end
4

What does the 'a mean?

5

This is an abstract type, which may be replaced by any one. You can compare 'a list with List<A> in java.

You also can use the abstract type and create a restricted one whih accept only one type of value :

type string_list = string list;;

This declaration create another one type, based on the existing one. It only tell the compiler to accept string in this list.

6

'a is usually read as ‘alpha’ and is syntactically a type variable. A type variable is a ‘stand-in’ for a type that will be filled in later. Type variables are usually also called generic types. You can read more here https://v1.realworldocaml.org/v1/en/html/a-guided-tour.html#inferring-generic-types

7

but the prime is necessary to define a type variable?

8

Yes. The syntax is covered in the link I gave above :slight_smile:

1 Like