two and unionWithKey.goDifferentHash are very similar

[sjakobi]

unordered-containers/Data/HashMap/Internal.hs

Lines 969 to 987 in 8c20f7a

	two :: Shift -> Hash -> k -> v -> Hash -> HashMap k v -> ST s (HashMap k v)
	two = go
	where
	go s h1 k1 v1 h2 t2
	| bp1 == bp2 = do
	st <- go (nextShift s) h1 k1 v1 h2 t2
	ary <- A.singletonM st
	return $ BitmapIndexed bp1 ary
	| otherwise = do
	mary <- A.new 2 $! Leaf h1 (L k1 v1)
	A.write mary idx2 t2
	ary <- A.unsafeFreeze mary
	return $ BitmapIndexed (bp1 .|. bp2) ary
	where
	bp1 = mask h1 s
	bp2 = mask h2 s
	idx2 | index h1 s < index h2 s = 1
	| otherwise = 0
	{-# INLINE two #-}

unordered-containers/Data/HashMap/Internal.hs

Lines 1668 to 1674 in 8c20f7a

	goDifferentHash s h1 h2 t1 t2
	| m1 == m2 = BitmapIndexed m1 (A.singleton $! goDifferentHash (nextShift s) h1 h2 t1 t2)
	| m1 < m2 = BitmapIndexed (m1 .|. m2) (A.pair t1 t2)
	| otherwise = BitmapIndexed (m1 .|. m2) (A.pair t2 t1)
	where
	m1 = mask h1 s
	m2 = mask h2 s

Maybe we can create a common abstraction, e.g. by changing the type of two:

 two :: Shift -> Hash -> HashMap k v -> Hash -> HashMap k v -> ST s (HashMap k v)

[sjakobi]

Once the Leaf for the first key-value pair is constructed early-on, we can also tweak two with the "shifted hash" tricks introduced in #458.