title: (OCaml) Strange syntax used in queue.ml -- The `<-` operator
body: <p>While browsing the Caml Light library for programming examples, I stumbled across the following code, taken from the Caml Light <code>queue.ml</code> file:</p>
  
  <pre><code>type 'a queue_cell =
      Nil
    | Cons of 'a * 'a queue_cell ref
  ;;
  
  type 'a t =
    { mutable head: 'a queue_cell;
      mutable tail: 'a queue_cell }
  ;;
  
  let add x = function
      { head = h; tail = Nil as t } -&gt;    (* if tail = Nil then head = Nil *)
        let c = Cons(x, ref Nil) in
          h &lt;- c; t &lt;- c
    | { tail = Cons(_, ref newtail) as oldtail } -&gt;
        let c = Cons(x, ref Nil) in
          newtail &lt;- c; oldtail &lt;- c
  ;;
  </code></pre>
  
  <p>This implementation of FIFO data structures puzzles me. I get the general idea, to keep a pointer to the last entry in the structure, so that appending at the end is possible. This makes perfect sense to me. However, it's the syntax of how this is done that bugs me.</p>
  
  <p>Consider the following:</p>
  
  <pre><code>  | { tail = Cons(_, ref newtail) as oldtail } -&gt;
        let c = Cons(x, ref Nil) in
          newtail &lt;- c; oldtail &lt;- c
  </code></pre>
  
  <p>I have a problem with types here. By the type definition, <code>newtail</code> should be of type <code>'a queue cell</code>, since it's retrieved using <code>Cons(_, ref newtail)</code> in the pattern matching: if I understand correctly, this would mean that <code>newtail</code> binds the <strong>value</strong> pointed by the second member of the <code>tail</code> record field (which originally is a reference).</p>
  
  <p>So what does the <code>newtail &lt;- c</code> means? If I try to replace this statement by <code>(fun x -&gt; x &lt;- c) newtail</code>, I get <code>The identifier x is not mutable.</code>, whereas the code sounds perfectly similar to the original variant to me.</p>
  
  <p>Would rewriting these few lines to read as follows mean the same?</p>
  
  <pre><code>  | { tail = Cons(_, newtail) as oldtail } -&gt;
        let c = Cons(x, ref Nil) in
          newtail := c; oldtail &lt;- c
  </code></pre>
  
  <p>Taking the question one step further, what does the following code actually do?</p>
  
  <pre><code>type t = Nil | Node of (t ref);;
  type box = {mutable field: t};;
  
  let poke = function
    | {field = Node(ref n)} -&gt; n &lt;- Nil
    | {field = Nil} -&gt; ()
  ;;
  
  let test = {field = Node(ref (Node(ref Nil)))};;
  poke test;;
  test;;
  </code></pre>
  
  <p>Is it the same to write</p>
  
  <pre><code>{field = Node(n)} -&gt; n := Nil
  </code></pre>
  
  <p>and</p>
  
  <pre><code>{field = Node(ref n)} -&gt; n &lt;- Nil
  </code></pre>
  
  <p>?</p>
  
  <p>Even stranger: the following code returns <code>The value identifier a is unbound.</code></p>
  
  <pre><code>let a = Nil;;
  a &lt;- Nil;; (* The value identifier a is unbound. *)
  </code></pre>
  
  <p>Could someone take the time to clarify the use of <code>&lt;-</code> for me? The various examples here are pretty puzzling to me...<br>
  Thanks! </p>
  
  <p><strong>EDIT: This was originally posted to the Caml Mailing list, but I thought the post didn't make it, so I posted it here. It appears that the posting did work; sorry for that: the link to the mailing list answer (which its original author also posted here), is <a href="https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00190.html" rel="nofollow">https://sympa-roc.inria.fr/wws/arc/caml-list/2011-01/msg00190.html</a>.</strong> </p>