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

John van Groningen johnvg at cs.ru.nl
Thu Apr 24 16:35:27 MEST 2008

Edsko de Vries wrote:

>Would it be easy to write a function
>  update_head :: *[.a] .a -> *[.a]
>  update_head = code inline { .. }
>which updates the head of a list in-place (given a spine-unique list, of
>course)? I feel it should be straightforward to someone who knows ABC
>code inside-out, but unfortunately I am not such a person.

The compiler can already perform such optimizations if compile option Reuse
Unique Nodes is enabled. So in most cases it is not necessary to write
abc code for such in-place updates.

If update_head would be defined as:

update_head :: *[.a] .a -> *[.a]
update_head [_:l] e = [e:l]

the compiler sees that the "[_:l]" cons node can be updated in place
to build "[e:l]". Unfortunately this is not possible in this case
because of the calling convention for update_head. If the result type
of a function is a list (or another algebraic data type) the function
is called with a node that has to be updated with the result. So in
the case of "update_head" this node will be overwritten with [e:l].

For example for this function:

update_head2 :: *[.a] .a -> (!*[.a],!Int)
update_head2 [_:l] e = ([e:l],0)

the compiler will update the "[_:l]" node to make a "[e:l]" node. The tuple
will be unboxed, so this function does not allocate any memory.

Kind regards,

John van Groningen

More information about the clean-list mailing list