Nem vagyok benne biztos, hogy immutable objektumoknál indokolt a deep copy. Elég csak azokat az objektumokat másolni, amiken van módosítás. Persze lehet, hogy van olyan usecase, ahol ez az állítás nem igaz, de - tapasztalataim alapján* - életképes az a megközelítés, hogy a nem módosított részgráfokat referencia szerint "másoljuk" be az új másolatba.
* nemrég összejött egy újraírható de immutable AST reprezentáció ennek alapján, nagyon büszke voltam rá :D