[Haskell-cafe] bimap 0.2

[Stuart Cook]

On Tue, Feb 5, 2008 at 9:11 PM, Neil Mitchell <ndmitchell at gmail.com> wrote:
> Hi
>
>
>  > The main difference is a pretty comprehensive interface shakeup: the
>  > Either variants have been dropped, all L variants have had the L
>  > removed from their name, and a few functions have been curried. The
>  > end result is an interface much closer to that of Data.Map. (This also
>  > means that 0.2 isn't backwards-compatible.)
>
>  Good, this seems much nicer. A few comments:
>
>  1) You depend on MTL, but I can't obviously see why. Perhaps the test suite?

The current implementation of (!) relies on the Monad instance for
Either exported by Control.Monad.Error. There's no fundamental reason
for this; it was just easier to code. Perhaps I'll get rid of it in a
later version, but I haven't bothered yet because I don't think an MTL
dependency is a big deal.


>  2) The code:
>
>  {-| Insert a pair of values into the bimap, without checking for
>  overlapping bindings. If either value is already in the bimap, and
>  is not bound to the other value, the bimap will become inconsistent.
>  -}
>  unsafeInsert :: (Ord a, Ord b)
>              => a -> b -> Bimap a b -> Bimap a b
>  unsafeInsert x y (MkBimap left right) =
>     MkBimap (M.insert x y left) (M.insert y x right)
>
>  To my understanding, this is always safe, since insert will overwrite
>  any existing element in a map. Hence you don't need to do the delete's
>  first. In addition, since Bimap is not exported internally, the
>  invariant will never be violated.

Consider the Bimap { (1, "alfa") }. If I do (unsafeInsert 1 "bravo"),
the left-hand map will contain:

  { (1 => "bravo") }

and the right-hand map will contain:

 { ("alfa" => 1), ("bravo" => 1) }

If I then do (lookupR "alfa"), I'll incorrectly get (Just 1) instead
of (Nothing).

Heck, let me prove it to you -- here's what happens if I define
(insert = unsafeInsert):

  prop_clobberR             : Falsifiable, after 0 tests:
  fromList [(-1,1)]
  0
  prop_valid                : Falsifiable, after 12 tests:
  fromList [(1,-5),(5,-5)]

It is true that at least one of the deletes will always be
unnecessary, but since a failed delete does nothing we might as well
leave both of them in.

The export of (valid) is mostly a debugging aid, so that users can
check whether their problems are caused by my code.


>  3)
>  insert x y = delete  x
>          >>> deleteR y
>          >>> unsafeInsert x y
>
>  Why not:
>
>  insert x y = unsafeInsert x y . delete x . delete y
>
>  Now you don't end up using the arrow combinators, and it becomes more
>  readable (at least to me). Of course, this function may disappear
>  entirely if what I wrote in (2) is correct.

This is a matter of taste, I guess. In this case I felt that the
"backwards" order of (.) was a little misleading, and I'm personally
quite comfortable with using (>>>) for forward composition.


>  I will probably start using the bimap package in my current project,
>  so you already have at least one user :-)

Glad to hear it, and thanks for your feedback.


Stuart