How to efficiently track and store deltas between two HAMTs

Ideally, I would like to be able to do

x = Map({'a': 2, 'c': 1})
y = x.update({'b': 3: 'c': 2)
z = y - x # magic
z == Map({'b': 3, 'c': 2})

Is there any particularly efficient way to do this in terms of memory and computational time? Ideally, I'd like z to share its data with y in the same way y shares its data with x. One way that comes to mind is

def diff(y, x):
  z = y
  for k, v in y.items():
    if k in x and x[k] == v:
      z = z.delete('k')
  return z

But this is O(N log N) (for log N get/set). Is there a more efficient way to go about this?

Không có tệp hoặc bài kiểm thử nào được nêu tên. Hãy bắt đầu bằng việc xem xét phần triển khai HAMT và Map cho update/delete, sau đó xác định liệu một biểu diễn delta có thể duy trì structural sharing mà không cần scan được đề xuất hay không. Được xem là hoàn thành khi có một cách tiếp cận hiệu quả, được ghi chép đầy đủ, hoặc một thay đổi API có phạm vi rõ ràng kèm coverage cho ví dụ.