set_monad_inefficiency.hs

import Data.Set.Monad as SM
import Debug.Trace as DT

(<+>) = liftM . plus
plus x y = DT.trace "." (x + y)

l = SM.fromList [0,1]

-- Intuitively expect 28 additions, but we actually get 60!
test = Set Int
test = do
  a <- l
  b <- a <+> l -- expect  4 additions, result [0..2]
  c <- b <+> l -- expect  6 additions, result [0..3], actually get  8 additions
  d <- c <+> l -- expect  8 additions, result [0..4], actually get 16 additions
  d <+> l      -- expect 10 additions, result [0..5], actually get 32 additions

Hit that with Codensity and see if it improves. Oh, no, I see now. It will actually improve but not in this way.