content: {-# LANGUAGE NoImplicitPrelude #-}
  
  module Numeric.Decidable.Nilpotent (DecidableNilpotent(..)) where
  
  import Data.Bits(Bits(..))
  import Data.Int(Int8,Int16,Int32,Int64)
  import Data.Word(Word8,Word16,Word32,Word64)
  import Numeric.Algebra
  import Numeric.Decidable.Zero
  import Prelude hiding (Num(..), Ord(..))
  
  -- | An element @x@ is nilpotent if there exists @n@ s.t. @pow1p x n@ is zero.
  class (Monoidal r, Multiplicative r) => DecidableNilpotent r where
      isNilpotent :: r -> Bool
  
  instance DecidableNilpotent () where
      isNilpotent _ = True
  
  instance DecidableNilpotent Bool where
      isNilpotent = isZero
  instance DecidableNilpotent Natural where
      isNilpotent = isZero
  instance DecidableNilpotent Integer where
      isNilpotent = isZero
  
  instance DecidableNilpotent Int where
      isNilpotent = signedBitsNilpotent
  instance DecidableNilpotent Int8 where
      isNilpotent = signedBitsNilpotent
  instance DecidableNilpotent Int16 where
      isNilpotent = signedBitsNilpotent
  instance DecidableNilpotent Int32 where
      isNilpotent = signedBitsNilpotent
  instance DecidableNilpotent Int64 where
      isNilpotent = signedBitsNilpotent
  instance DecidableNilpotent Word8 where
      isNilpotent = unsignedBitsNilpotent
  instance DecidableNilpotent Word16 where
      isNilpotent = unsignedBitsNilpotent
  instance DecidableNilpotent Word32 where
      isNilpotent = unsignedBitsNilpotent
  instance DecidableNilpotent Word64 where
      isNilpotent = unsignedBitsNilpotent
  
  instance (DecidableNilpotent a, DecidableNilpotent b) => DecidableNilpotent (a,b) where
      isNilpotent (a,b) = isNilpotent a && isNilpotent b
  
  instance (DecidableNilpotent a, DecidableNilpotent b, DecidableNilpotent c) => DecidableNilpotent (a,b,c) where
      isNilpotent (a,b,c) = isNilpotent a && isNilpotent b && isNilpotent c
  
  instance (DecidableNilpotent a, DecidableNilpotent b, DecidableNilpotent c, DecidableNilpotent d) => DecidableNilpotent (a,b,c,d) where
      isNilpotent (a,b,c,d) = isNilpotent a && isNilpotent b && isNilpotent c && isNilpotent d
  
  instance (DecidableNilpotent a, DecidableNilpotent b, DecidableNilpotent c, DecidableNilpotent d, DecidableNilpotent e) => DecidableNilpotent (a,b,c,d,e) where
      isNilpotent (a,b,c,d,e) = isNilpotent a && isNilpotent b && isNilpotent c && isNilpotent d && isNilpotent e
  
  unsignedBitsNilpotent :: (Bits r, Group r, Unital r) => r -> Bool
  unsignedBitsNilpotent b = (b /= one) && b .&. (b - one) == zero
  
  signedBitsNilpotent :: (Bits r, Group r, Order r, Bounded r, Unital r) => r -> Bool
  signedBitsNilpotent b | zero <~ b = unsignedBitsNilpotent b
                        | otherwise = b == minBound ||
                                      unsignedBitsNilpotent (negate b)
  
  