search

nominolo / union-find

Efficient union and equivalence testing of sets.
Other
29 stars 12 forks source link

You can violate constraints with `Data.UnionFind.IntMap` #2

Open tel opened 10 years ago

tel commented 10 years ago

Like so

bug :: ()
bug = 
  let pt = evalState (state (fresh ()))
      v = descriptor newPointSupply pt
  in v

Now, arguably this is just the fault of the user. I'd like to entertain the idea that it's a deficiency in the API. Since Points are only meaningful in reference to a particular value of type PointSupply it's possible for them to "travel back in time". In other words, the semantics of the types of this API cannot forbid time travel.

Which would just be unfortunate, except there's a perfectly wonderful way to solve this problem by using the same phantom type variable trick that ST uses. It would require actually producing the monadic interface instead of leaving it thinly available from the types of the API, of course.

(Interestingly, this bug can be seen as inevitable in the code itself since IntMap.! is used without ensuring its invariants hold.)

In particular, I'd like to highlight this issue for this package as I ran into this problem elsewhere (in a Javascript library I'm writing) and now I'm writing up a series of blog posts to highlight it. I chose Union/Find as an algorithmic example and looked up to find this package.

Since the point of the post is to culminate in calling out this API bug and encouraging more people to use ST-style phantom variables, I wanted to give a forewarning in the event you would like to update documentation or API.

Finally, if it's not worth the added complexity in the API, I totally understand. I don't intend to call out this module specifically by any means. It's a perfectly good toolset for the proper use of an IntMap-backed Union/Find, but simply requires a little care.

nominolo commented 10 years ago

Thanks for the heads up. It shouldn't be too hard to add an ST-like layer around the less safe API. I'll keep it in mind.