On Sat, Jun 21, 2008 at 11:54 PM, Adrian Hey
Hello apfelmus,
apfelmus wrote:
I've never been very keen on alter myself (on efficiency grounds) and was wondering whether of not to include it. If the "altering" results in an unchanged map it would be nice to just return the unchanged map (rather than duplicate all nodes on the search path). There are other possible alternatives to alter that are more efficient in this respect.
You mean the case when
f Nothing = Nothing
or, for some a ..
f (Just a) = Just a
..but of course there's no way you can tell from inside the alter function that the two a's are the same without an expensive equality test, and even then that's not enough because you need to pass the "no change" information back up the call chain (as a Nothing probably) which means that if there is a change even more heap will be burned by wrapping each intermediate result in a Just.
Thinking as a C++ programmer for a bit, I'd want to implement this as a pointer comparison. If the argument to alter returns the same object (not just an equal one), then the implementation can cheaply avoid creating the new sub-tree. If it returns an equal one, you'd like to skip the copy, but it's not worth the equality test. Is there a reason I'm missing that it's a bad idea to use GHS.Prim.reallyUnsafePtrEquality# or a similar low-level function in the alter implementation? If alter were to cheat like this, we'd want to write its argument as: f n@Nothing = n f j@(Just a) = j instead of risking creating a new object. Trying this out, I figured out why it's called "reallyUnsafe": Prelude GHC.Exts GHC.Prim> let q = Just 3 Prelude GHC.Exts GHC.Prim> let f j@(Just a) = j; r = f q Prelude GHC.Exts GHC.Prim> I# (reallyUnsafePtrEquality# q r) 0 Prelude GHC.Exts GHC.Prim> r Just 3 Prelude GHC.Exts GHC.Prim> I# (reallyUnsafePtrEquality# q r) 1 Prelude GHC.Exts GHC.Prim> and even stranger: Prelude GHC.Exts GHC.Prim> let q = Just 3 Prelude GHC.Exts GHC.Prim> let f j@(Just a) = j; r = f q Prelude GHC.Exts GHC.Prim> I# (r `seq` reallyUnsafePtrEquality# q r) 0 Prelude GHC.Exts GHC.Prim> I# (r `seq` reallyUnsafePtrEquality# q r) 1 So it'd take some doing to get the implementation right, but getting the fully-general API without wasting allocations might be worth it. Jeffrey