Z_n in Haskell
Hal Daume III
Thu, 28 Mar 2002 13:27:42 -0800 (PST)
Suppose I want to define integers modulo n, I could do this something
data Zn = Zn Integer Integer -- modulus, number
instance Num Zn where
(Zn m1 n1) + (Zn m2 n2)
| m1 == m2 = Zn m1 (n1 + n2 `mod` m1)
| otherwise= error "differing moduli"
However, I'd really like it if, say, addition on Zn-s of different
"n" values were caught by the typechecker and disallowed. One solution to
this problem would be to do something like:
class Modulus m where modulus :: T m -> Integer
data Zn m = Zn (T m) Integer
instance Modulus m => Num (Zn m) where
(Zn m1 n1) + (Zn m2 n2) =
(Zn m1 ((n1 + n2) `mod` (modulus m1)))
data T a = T
instance Modulus (Mod5) where modulus _ = 5
instance Modulus (Mod7) where modulus _ = 7
then we get:
Modulus> (Zn (T :: T Mod5) 3) + (Zn (T :: T Mod5) 4)
but it fails when the moduli are different:
Modulus> (Zn (T :: T Mod5) 3) + (Zn (T :: T Mod7) 4)
Ambiguous type variable(s) `a' in the constraint `Show a'
arising from use of `print' at <No locn>
In a 'do' expression pattern binding: print it
Couldn't match `Mod7' against `Mod5'
Expected type: T Mod7
Inferred type: T Mod5
In an expression with a type signature: T :: T Mod7
In the first argument of `Zn', namely `(T :: T Mod7)'
Unfortunately, this solution isn't very pretty. We have to define a new
datatype for each modulus and make it an instance of Modulus. Is there a
better way to do this?
Hal Daume III
"Computer science is no more about computers | firstname.lastname@example.org
than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume