Haskell Nim calculation

gistfile1.hs

module Data.Nim
(Nim)
where

import Data.Bits

class Nim a where
    (+^*) :: a -> a -> a
    (*^*) :: a -> a -> a
  
instance Nim Integer  where
  a +^* b = a `xor` b
  a *^* b = nimMul a b

nimMul :: (Bits a, Enum a, Eq a, Num a) => a -> a -> a
nimMul _ 0 = 0 
nimMul 0 _ = 0 
nimMul x 1 = x -- for efficiency
nimMul 1 y = y -- for efficiency
nimMul x y = mex [ (nimMul x b) `xor` (nimMul a y) `xor` (nimMul a b) | a<-[0..(x-1)], b<-[0..(y-1)]] !! 0

-- helper functions

-- diff sets
-- ex)
-- [3, 10, 7] -> [0, 1, 2, 4, 5, 6, 8, 9, 11, 12, 13, ...] 
exclusiveList :: (Enum a, Eq a, Num a) => [a] -> [a]
exclusiveList z = foldr (λx y -> if elem x z then y else x:y) [] [0..]

-- mex z is the smallest ordinal which is not an element of z.
-- ex)
-- [0, 1] -> [2]
-- [1, 2] -> [0] 
mex :: (Enum a, Eq a, Num a) => [a] -> [a]
mex z = take 1 $ exclusiveList z