You don't have to mutate them. You can create a new persistent variant and just mutate the ref to point to the new one. Users of that "variable" store the ref instead of the value (well, actually, they get the choice of which to do). If users have held on to references to the old values, the GC doesn't collect them. If they haven't, the GC can collect them just like any other circumstance involving persistent data structures.