Linked List Ocaml

Question

How would i create a linked list to hold my data in Ocaml? Im trying to make a singly linked list, however im having trouble with the syntax. I just want to make a module to simply get the 'a from the linked list, insert 'a or delete 'a.

Anyone have any idea?

Thanks, Faisal Abid

Answer 1

Doesn't OCaml already have lists as a primitive? I haven't done SML since college, but I seem to recall head and tail primitives. I see that other people have implemented a true linked list data structure out there though... check out Dustin's OCaml Linkedlist for example.

Answer 2

OCaml has lists built in:

List of integers: [1;2;3;4;5] ;; returns: int list = [1; 2; 3; 4]

List of Strings: ["this";"that";"other"];; returns: string list = ["this"; "that"; "other"]

Or you can use the cons operator :: to build lists:

1::2::3::[];; returns: int list = [1; 2; 3]

To get the head (first item) of a list:

List.hd [1;2;3]
returns 1

To get the tail of a list (all items after the first item)

List.tl [1;2;3] returns: int list = [2; 3]

Also, you can have a look at how lists are implemented in the OCaml standard library by looking at:

[installation location for OCaml]/lib/ocaml/std-lib/list.ml

Answer 3

As aneccodeal told, ocaml already has lists.

However, for your interest, this is how you could build your own list. Obviously, you would never use it on a real application :) If you want to have some trees, the data structure would be very similar.

exception Empty_list

type 'a my_list = Nil | List of 'a * 'a my_list

let head = function 
     Nil -> raise Empty_list
   | List(e,_) -> e;;

let tail = function
    Nil -> Nil
   | List(_,t) -> t

let l = List(1, List(4, List(8, Nil)));;

print_endline (string_of_int(head l));;

print_endline (string_of_int (head(tail l)));;