let insert (m, s, d_opt) (k,v) = (M.add k v m, S.remove k s, d_opt)