I think the extra allocation can be neglected. For very small containers, lists and alists can't be beaten. For larger containers where it makes sense to use mappings, sets, etc., the extra allocation is irrelevant. Moreover, it is not necessarily an extra indirection. For a tree-like data structure, one can simply use the tree's root.
Agreed that extra allocation can be neglected.
On a tree structure - If we don't use indirection, we need at least to copy the root node, right?
Say, we have a set based on tree, and we have something as {1 . {2 . 3}}. We pass it to a functional delete procedure to remove '1'. The functional delete procedure can't return the subtree {2 . 3} directly, for it may be passed to mutators, so either it needs to copy the root node (of the subtree).
Anyway, it is covered by "non-eqv?" requirements. It may be odd for those who come from the functional world, but the more I think about it, the more it seems to make sense.