Use "smart initialization" trick in more places

[sjakobi]

#359 introduced a trick that replaces a write to an array by initializing the array with the same element. We can use the same trick in some more places:

• insertNewKey.snocNewLeaf (refactor to use snoc #407):

  unordered-containers/Data/HashMap/Internal.hs

  Lines 828 to 833 in f59bb26

  	snocNewLeaf :: Leaf k v -> A.Array (Leaf k v) -> A.Array (Leaf k v)
  	snocNewLeaf leaf ary = A.run $ do
  	let n = A.length ary
  	mary <- A.new_ (n + 1)
  	A.copy ary 0 mary 0 n
  	A.write mary n leaf

• insertModifyingArr (refactor to use snoc #407) :

  unordered-containers/Data/HashMap/Internal.hs

  Lines 1008 to 1025 in f59bb26

  	insertModifyingArr :: Eq k => v -> (v -> (# v #)) -> k -> A.Array (Leaf k v)
  	-> A.Array (Leaf k v)
  	insertModifyingArr x f k0 ary0 = go k0 ary0 0 (A.length ary0)
  	where
  	go !k !ary !i !n
  	| i >= n = A.run $ do
  	-- Not found, append to the end.
  	mary <- A.new_ (n + 1)
  	A.copy ary 0 mary 0 n
  	A.write mary n (L k x)
  	return mary
  	| otherwise = case A.index ary i of
  	(L kx y) | k == kx -> case f y of
  	(# y' #) -> if ptrEq y y'
  	then ary
  	else A.update ary i (L k y')
  	| otherwise -> go k ary (i+1) n
  	{-# INLINE insertModifyingArr #-}

• updateOrSnocWithKey (refactor to use snoc #407) :

  unordered-containers/Data/HashMap/Internal.hs

  Lines 2161 to 2178 in f59bb26

  	updateOrSnocWithKey :: Eq k => (k -> v -> v -> (# v #)) -> k -> v -> A.Array (Leaf k v)
  	-> A.Array (Leaf k v)
  	updateOrSnocWithKey f k0 v0 ary0 = go k0 v0 ary0 0 (A.length ary0)
  	where
  	go !k v !ary !i !n
  	| i >= n = A.run $ do
  	-- Not found, append to the end.
  	mary <- A.new_ (n + 1)
  	A.copy ary 0 mary 0 n
  	A.write mary n (L k v)
  	return mary
  	| L kx y <- A.index ary i
  	, k == kx
  	, (# v2 #) <- f k v y
  	= A.update ary i (L k v2)
  	| otherwise
  	= go k v ary (i+1) n
  	{-# INLINABLE updateOrSnocWithKey #-}

• Strict.updateOrSnocWithKey

[konsumlamm]

Just a thought: It might be worth documenting this trick (and other, similar ones) in CONTRIBUTING.md, so that people use it in their contributions and understand the existing uses.

[sjakobi]

Thanks for the suggestion! I agree that implementation tricks and tweaks should be documented better. What do you think about GHC's NOTE system? I have tried to use it in prettyprinter a bit, but I don't really have a comparison to different systems.

[konsumlamm]

I'm not really familiar with GHC's NOTE system. If there's a way to look at the notes other than reading the source code, then that's great! If the notes were only available in the source code, I think that wouldn't be very discoverable.

[sjakobi]

I think it's an advantage of GHC-style notes that they are located so closely to the code. This way the surrounding code provides context which is helpful for understanding the note.

[sjakobi]

Regarding the code patterns from the issue description: I think all of these could be refactored to use a new Array.snoc operation.

snoc :: Array a -> a -> Array a

[sjakobi]

One task left: Strict.updateOrSnocWithKey