data A = Done !Word | Partial !Word

-- non-associative
instance Magma A where
    magma = m
      where
        m (Done x) (Done y) = Done (min x y)
        m (Done x) Partial{} = Done x
        m Partial{} (Done y) = Done y
        m (Partial x) (Partial y) = Done (xor x y)
    {-# INLINE magma #-}

type B = Int

tip :: Word -> B -> A
tip w b
    | b >= 2 = Done 0
    | otherwise = Partial w
{-# INLINE tip #-}

ins :: Maybe B -> Maybe B
ins = Just . maybe 1 (+ 1)
{-# INLINE ins #-}

del :: Maybe B -> Maybe B
del ma = case ma of
    Just a | a > 1 -> Just (a - 1)
    _ -> Nothing
{-# INLINE del #-}

insert :: (KnownNat h) => Word -> Trie h A B -> Trie h A B
insert = alterWith tip ins
{-# INLINE insert #-}

delete :: (KnownNat h) => Word -> Trie h A B -> Trie h A B
delete = alterWith tip del
{-# INLINE delete #-}

magmaAll :: Trie h A B -> Maybe A
magmaAll = magmaAllWith tip
{-# INLINE magmaAll #-}