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

[John van Groningen]

Hi Edsko,

>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

It is not. You specified the type of ones, therefore ones is a function.
You probably want something like:

let ones_ = [1:ones_] // cycle, shared node
   
    ones :: *[Int]
    ones = ones_      // function

>  - 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?

See above.

There is such a command line option for the Linux compiler: -ou

>..
>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?

updhead2 will update the node in place, but updhead will copy this node.

Kind regards,

John van Groningen