Under the hood I'm going to use Rust `Vec<T>`s to represent lists, so it'd be trivial to provide a FFI operation to append something to the end in constant time. However, we can treat the list like a linked list, and, using recursion, here's a tail-call-optimized implementation of append in linear time:
append = list value -> {
loop = acc rem -> match rem {
[] -> acc,
[head & tail] -> loop [head & acc] tail
}
loop value (List::reverse list)
}
I'm thinking of using something other than the `[a & b]` syntax, but that's besides the point. Note that `loop` does not close over any values other than itself, so it doesn't need to be inside `append`:
loop = acc rem -> ...
append = list value -> ...
The function really starts when we reach this line:
loop value' (List::reverse list')
I added `'` to indicate that this is the last occurrence of both `list` and `value` in this scope, which means that they're passed to `loop` without making a CoW reference. Let's look at `loop`:
loop = acc rem -> match rem {
[] -> acc,
[head & tail] -> loop [head & acc] tail
}
This is where things get complicated, depending on the definition of match. If it were defined as macro, it'd be laborious to write out how it all works by hand. But if we treat `loop` as a function with multiple heads, it's a bit easier.
Here, we have two arms. If the remaining list is empty, we return `acc`. note that each arm is independent, so this usage of `acc` is the last in the scope.
If the list is not empty, we match `rem` against `[head & tail]`. This is equivalent to, roughly:
[head & tail] = rem'
Note how this is the last usage of rem in this scope, meaning it's passed by actual value. This list is then split in-place, with head taking on the value of the first element of the list and tail taking on the value of the rest. Once passed to loop, note that all the values used are the last occurrence of the value in the scope:
loop [head' & acc'] tail'
This means that the actual value is passed down to the next level. Looking at this as a whole, we can see that nothing is ever passed by CoW reference, which means that this operation is performed in-place. And because it's done in a tail-recursive manner, `append` only uses constant space.
So to answer your question specifically: what if append is called with `xs` being a CoW reference?
append &xs y
When we reach the line:
[head & tail] = &rem'
`rem` is mutated, i.e. split in two, so a copy of it is made. This copy is it's own value, so head no tail are no longer CoW. we then call:
loop [head & acc] tail
Note that head and tail are now passed by value and not CoW - same goes for acc. Because nothing is CoW anymore, this tail-recursive implementation operates on the new list, mutating it in place.
In short: the first iteration in `append` makes a copy to the list, but in subsequent iterations the copy is used, and the list is mutated in place.
That was a big one, I'm practically writing the blog post out here, haha! Does this help clear things up?