search

joelwilliamson / bimap

Bidirectional mapping between two key types
BSD 3-Clause "New" or "Revised" License
22 stars 8 forks source link

Add update functions, inspired from Data.Map API #2

Closed k0ral closed 9 years ago

joelwilliamson commented 9 years ago

Could you add some tests?

(lookup k $ adjust f k m) == (f <$> lookup k m)

and

(adjust f_inverse k $ adjust f k m) == m

seem like they are valid properties.

joelwilliamson commented 9 years ago

I don't think this is correct. When you adjust a value in the l map, you should also need to adjust the key in the r map (and vice versa). lookupR (lookup k m) m == return k will fail after making an adjustment.

k0ral commented 9 years ago

Indeed, this was shamefully wrong, sorry for that. I've updated the pull request to get what I think is the expected behavior. Notably, I don't think we want to have (adjust f_inverse k $ adjust f k m) == m. Because of the bijectivity constraint, adjust f k m :: Bimap a b may have to delete some a element, that adjust f_inverse k won't be able to recreate. Do we agree on that point ?

joelwilliamson commented 9 years ago

Agree.

Data.Map also implements adjustWithKey:: (k -> a -> a) -> k -> Map k a -> Map k a. Do you think that would be useful to have for a Bimap?

k0ral commented 9 years ago

It makes sense. While I was at it, I also added the serie of update functions. Please double check the code, a lot of copy-pasting was involved in the process :) .

joelwilliamson commented 9 years ago

I'm seeing a bug in adjustR that I don't understand.

let bi = fromList [(0,-3)]
let f = (3*)
let showFull bi = "L: " ++ show (toMap bi) ++ "\tR: " ++ show (toMapR bi)
showFull $ adjustR f (-3) bi
> L: fromList [(0,-3)]    R: fromList []
k0ral commented 9 years ago

I've just fixed it:

let bi = fromList [(0,-3)]
let f = (3*)
let showFull bi = "L: " ++ show (toMap bi) ++ "\tR: " ++ show (toMapR bi)
putStrLn $ showFull $ adjustR f (-3) bi
> L: fromList [(0,-3)]  R: fromList [(-3,0)]
joelwilliamson commented 9 years ago

I've added these changes to the version on Hackage.