monoid.hs

import Data.Semigroup (stimes)

newtype Product = Product Integer

instance Semigroup Product where
  Product x <> Product y = Product $ x * y

instance Monoid Product where
  mempty = Product 1

-- Implementing exponentiation by hand with N multiplications
-- *Main> let (Product x) = iterate (<> Product 2) (Product 2) !! 1000000 in x `mod` 10
-- 2 (very slowly)

-- Letting Haskell do it in log(N) multiplications via repeated squaring
-- *Main> let (Product x) = stimes 10000001 (Product 2) in x `mod` 10
-- 2 (very quickly)