Linked list in ocaml

Learning
1

Below the code for a linked list.

type node={
    value:int;
    mutable next:node option;
    }

type mlist={
    mutable first:node option;
    }

let create_node v : node={
    next:node option=None;
    value=v;
    }

let singleton v:mlist={
    first:node option = Some (create_node v)
    }

let insert_first lst v=match lst.first with
    | None -> lst.first <-Some (create_node v);
    | Some was_first ->
         let new_first = create_node v in
         new_first.next<-Some was_first;
         lst.first<-Some new_first

let empty () : mlist ={
    first=None
    }

let n1:mlist=empty();;
insert_first n1 1;;
let n2:mlist=singleton 2;;
insert_first n2 1;;

Two small questions.
One how do i create a print functions which traverses the list a print the values.
Two how does the function create node returns a node when there is not a variable node created nor returned by the function. In fact the last line is an int. Is it “inferred” by the compiler.

2

how do i create a print functions which traverses the list a print the values.

A while loop seems like the simplest way. It will be a bit of a hassle to express but that arises naturally from the data structure.

how does the function create node returns a node when there is not a variable node created nor returned by the function.

There actually is a node value returned by the function. node is a record type which is constructed using the record literal syntax, { next = ...; value = ... }. Since OCaml is not whitespace-sensitive, you can spread out the record syntax over multiple lines:

let create_node v = {
  next = None;
  value = v;
}

In fact the last line is an int. Is it “inferred” by the compiler.

Which leads us to the second realization, the last line of this function is not an int, it’s just part of the record literal as we said above. In fact in an expression-oriented language like OCaml, the concept of ‘last line of the function’ is not very useful. It is more useful to think in terms of expressions. The entire function body is a single expression which is a record literal.

This actually leads me to another question–why define a list like this in OCaml when there is a built-in immutable list type? Is it for educational reasons?

3

Thanks, that explains. My knowledge of C had put me on the wrong leg as { } has different meaning.
I came across this code in this nice online course,

4

I expected next program to print 1,2,3,4,5. Instead it prints 2,5,3

type node={
    value:int;
    mutable next:node option;
    }

type mlist={
    mutable first:node option;
    }

let create_node v : node={
    next:node option=None;
    value=v;
    }

let singleton v:mlist={
    first:node option = Some (create_node v)
    }

let insert_first lst v=match lst.first with
    | None -> lst.first <-Some (create_node v);
    | Some was_first ->
         let new_first = create_node v in
         new_first.next<-Some was_first;
         lst.first<-Some new_first

let empty () : mlist ={
    first=None
    }

let n1:mlist=empty();;
insert_first n1 1;;
insert_first n1 2;;
let n2:mlist=singleton 3;;
insert_first n2 4;;
insert_first n2 5;;

let print_node (n:node)  =
    print_int n.value;;

let print_mlist (m:mlist) =
    let no:node option ref =ref m.first in 
    while not (!no=None) do 
        match !no with 
        | None -> ()
        | Some n -> let () = print_node n in 
                    match n.next with
                    | None ->   no:=None
                    | Some x -> no:=x.next     
    done;;

print_mlist n1;;
print_mlist n2;;
1 Like
5

Subtle logic error. Your algorithm is skipping every other node. Fix:

let print_mlist (m:mlist) =
    let no:node option ref =ref m.first in 
    while not (!no=None) do 
        match !no with 
        | None -> ()
        | Some n -> let () = print_node n in 
                    match n.next with
                    | None ->   no:=None
-                   | Some x -> no:=x.next
+                   | Some x -> no:=n.next
    done

Or to simplify it a bit more:

let print_mlist mlist =
  let no = ref mlist.first in
  while Option.is_some !no do
    let n = Option.get !no in
    print_node n;
    no := n.next
  done
1 Like