Create a type for each Integer in Haskell?

Question

I would like to create a data type in Haskell that represents the integers mod n, and which is an instance of Num to help perform simple modular arithmetic operations. My first attempt at this looked like this

data Z n e = El n e
instance (Show n, Show e) => Show (Z n e) where
    show (El n e) = show e ++ " (mod " ++ show n ++ ")"

instance (Integral k, Integral e) => Num (Z k e) where
    (+) (El n a) (El m b) = El n (mod (a + b) n)
    (-) (El n a) (El m b) = El n (mod (a - b) n)
    (*) (El n a) (El m b) = El n (mod (a * b) n)
    negate (El n a) = El n (mod (0 - a) n)
    abs (El n a) = El n a
    signum (El n a) = El n a
    fromInteger i = -- problematic...

This compiles but is problematic not only because its unclear how to implement fromInteger since k is out of scope, but also because it is permissible to add an integer mod 4 with an integer mod 5 without a type error. In my second attempt I tried to resolve these issues

data Z n = El Integer
instance (Show n) => Show (Z n) where
    show (El n e) = show e ++ " (mod " ++ show n ++ ")"

instance (Integral k) => Num (Z k) where
    (+) (El k a) (El k b) = El k (mod (a + b) k)
    (-) (El k a) (El k b) = El k (mod (a - b) k)
    (*) (El k a) (El k b) = El k (mod (a * b) k)
    negate (El k a) = El k (mod (0 - a) k)
    abs (El k a) = El k a
    signum (El k a) = El k a
    fromInteger i = El (fromIntegral i) k

but I am running into trouble implementing the Num interface because of conflicting definitions of k which is still out of scope. How can I make such a data type in Haskell?

Answer 1

As noted in the comments, the idea is to make use of a type-level representation of natural numbers, so you have separate identifiable types for 2 versus 3 versus 4, etc. This requires an extension:

{-# LANGUAGE DataKinds #-}

There are two main methods for representing naturals as types. The first is to define a recursive data type:

data Nat' = Z | S Nat'

which the DataKinds extension automatically lifts to the type level. You can then use this as, among other things, a type-level tag to define a family of related but distinct types:

{-# LANGUAGE KindSignatures #-}
data Foo (n :: Nat') = Foo Int

twoFoo :: Foo (S (S Z))
twoFoo = Foo 10

threeFoo :: Foo (S (S (S Z)))
threeFoo = Foo 20

addFoos :: Foo n -> Foo n -> Foo n
addFoos (Foo x) (Foo y) = Foo (x + y)

okay = addFoos twoFoo twoFoo
bad =  addFoos twoFoo threefoo -- error: different types

The second is to use a built-in GHC facility that automatically lifts integer literals, like 2 and 3 to the type level. It works much the same way:

import GHC.TypeLits (Nat)

data Foo (n :: Nat) = Foo Int

twoFoo :: Foo 2
twoFoo = Foo 10

threeFoo :: Foo 3
threeFoo = Foo 20

addFoos :: Foo n -> Foo n -> Foo n
addFoos (Foo x) (Foo y) = Foo (x + y)

okay = addFoos twoFoo twoFoo
bad =  addFoos twoFoo threefoo -- type error

When you're using naturals only to "tag" a type, it's generally more convenient to use the GHC.TypeLits version of Nat. If you have to actually do type-level computations on the types, some computations are more easily done using the recursive version.

Since we only need the naturals as tags, we can stick with the GHC.TypeLits solution. So, we'd define your data type like so:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
import GHC.TypeLits
data Z (n :: Nat) = El Integer

In the Show instance, we need to make use of some other facilities in GHC.TypeLits to convert the type-level Nat to a value-level Integer that we can include in the printed representation:

instance (KnownNat n) => Show (Z n) where
  show el@(El e) = show e ++ " (mod " ++ show (natVal el) ++ ")"

There's magic going on here! The natVal function has signature:

natVal :: forall n proxy. KnownNat n => proxy n -> Integer

meaning that for a "KnownNat", whatever that means, it can take a proxy value whose type is of form proxy n, and return the actual integer corresponding to the type-level argument n. Fortunately, our original element has type Z n which fits the proxy n type pattern just fine, so by running natVal el, we get the value-level Integer corresponding to the type-level n in Z n.

We'll use the same magic in the Integral instance:

instance (KnownNat k) => Num (Z k) where
    (+) el@(El a) (El b) = El (mod (a + b) k) where k = natVal el
    (-) el@(El a) (El b) = El (mod (a - b) k) where k = natVal el
    (*) el@(El a) (El b) = El (mod (a * b) k) where k = natVal el
    negate el@(El a) = El (mod (0 - a) k) where k = natVal el
    abs el@(El a) = El a where k = natVal el
    signum el@(El a) = El 1
    fromInteger i = El (fromIntegral i)

Note that the k disappears from the El constructor, because it's not a data-level quantity. Where needed, it can be retrieved using natVal el using the KnownNat instance.

The full program is:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
import GHC.TypeLits
data Z (n :: Nat) = El Integer

instance (KnownNat n) => Show (Z n) where
  show el@(El e) = show e ++ " (mod " ++ show (natVal el) ++ ")"

instance (KnownNat k) => Num (Z k) where
    (+) el@(El a) (El b) = El (mod (a + b) k) where k = natVal el
    (-) el@(El a) (El b) = El (mod (a - b) k) where k = natVal el
    (*) el@(El a) (El b) = El (mod (a * b) k) where k = natVal el
    negate el@(El a) = El (mod (0 - a) k) where k = natVal el
    abs el@(El a) = El a where k = natVal el
    signum el@(El a) = El 1
    fromInteger i = El (fromIntegral i)

and it works as intended:

> :set -XDataKinds
> (El 2 :: Z 5) + (El 3 :: Z 5)
0 (mod 5)
> (El 2 :: Z 5) + (El 3 :: Z 7)

<interactive>:15:18: error:
    • Couldn't match type ‘7’ with ‘5’
      Expected type: Z 5
        Actual type: Z 7
    • In the second argument of ‘(+)’, namely ‘(El 3 :: Z 7)’
      In the expression: (El 2 :: Z 5) + (El 3 :: Z 7)
      In an equation for ‘it’: it = (El 2 :: Z 5) + (El 3 :: Z 7)