How delete for Map should be.

delete.hs

import Data.Map (Map)
import Data.Map as Map

--------------------------------------------------------------------------------
-- | I'm bad at naming thing however, we are going to use that datastructure
--  so we could lookup and delete in one single pass.
data Blob a b = Blob a b

--------------------------------------------------------------------------------
instance Functor (Blob a) where
  fmap f (Blob a b) = Blob a (f b)

--------------------------------------------------------------------------------
deleteMap :: k -> Map k v -> (Maybe v, Map k v)
deleteMap key ms =
  let Blob result newMs =
        Map.alterF go key ms in
        (result, newMs)
  where
    go Nothing  = Blob Nothing Nothing
    go (Just e) = Blob (Just e) Nothing