[clean-list] Update head of the list in-place?

[Edsko de Vries]

Hi John,

Thanks for your reply. The reason for my question is that I was trying
to come up with an example that showed that one has to be careful with
uniqueness and recursion. According to "Uniqueness Typing for Functional
Languages with Graph Rewriting Semantics", typing rule for letrec, a
recursively defined object must be non-unique. This rule makes sense to
me, but I was trying to come up with a simple example that would show
what would go wrong if this restriction was not added.  

Now, using your definition of updhead2, I defined the following module: 

  module updhead
  
  updhead2 :: *[.a] .a -> (!*[.a], !Int)
  updhead2 [_:xs] x = ([x:xs], 0)
  
  Start = let ones :: *[Int]
              ones = [1 : ones]
          in updhead2 ones 2

My thinking was:

  - The compiler must reject the definition of ones (in particular, its type)
    because it is a recursively defined object
  - If the compiler does *not* reject the definition of ones, *and* updhead2
    does in fact update the head of the list in-place, then the result of the
    program will to be [2, 2, 2, ...] rather than the expected [2, 1, 1, ...]
    (which is exactly the reason why the type of ones should be rejected).

However, to my surprise, the Clean compiler *did* accept the definition
of 'ones'. First I thought I had unearthed a bug in the type checker.
But then when I ran the program, I had another surprise: the result of
the program is [2, 1, 1, ...].

So either updhead2 is not actually updating the list in-place (I tried
this on a mac with Reuse unique nodes enabled; I couldn't find the
appropriate command line option for the Linux compiler -- is there
one?), or there's an error in my thinking somewhere. Can you clarify?

Thanks for your feedback,

Edsko

PS. If updhead2, above, does in fact update the list in-place, would it
be possible to define

  updhead = fst o updhead2

to obtain the function that updates the head of a list in place? or
would the compiler "optimize" this to subsequently loose the possibility
to reuse the unique node, due to the calling convention?