在Haskell中为每个整数创建一个类型?

3

我希望在Haskell中创建一个数据类型,表示模数为n的整数,并使其成为Num的实例,以便执行简单的模算术操作。我的第一次尝试如下:

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...

这段代码虽然可以编译,但存在问题。不仅因为无法确定如何实现fromInteger函数,因为k超出了其作用域,而且还因为它允许将一个取模4的整数和一个取模5的整数相加,而不会产生类型错误。在我的第二次尝试中,我试图解决这些问题。

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

但我在实现Num接口时遇到了麻烦,因为k的定义冲突仍然超出范围。我如何在Haskell中创建这样的数据类型?


5
你需要在类型级别上表示数字。Integral k 意味着 k 是一个包含整数(或类似整数)的类型,但你想表达的是 k 本身就是一个整数。请查阅关于类型级别自然数的相关资料,有很多可供参考。 - luqui
1
啊,谢谢,这非常有帮助。我的问题之一是不知道正确的术语来描述搜索。 - Jon Deaton
2
这个 - Daniel Wagner
请查看此链接:http://hackage.haskell.org/package/modular-arithmetic-1.2.1.5/docs/Data-Modular.html。 - leftaroundabout
1个回答

1

如评论中所述,这个想法是利用自然数的类型级表示,因此您可以拥有单独可识别的类型,例如2与3与4等。 这需要一种扩展:

{-# LANGUAGE DataKinds #-}

将自然数表示为类型有两种主要方法。第一种是定义递归数据类型:

data Nat' = Z | S Nat'

DataKinds 扩展自动将其提升到类型级别。然后,您可以将其用作类型级别标记,以定义一系列相关但不同的类型。

{-# 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

第二种方法是使用 GHC 内置的功能,自动将整数字面量(如23)提升到类型级别。它的工作方式与第一种方法类似:
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

当您仅使用自然数“标记”类型时,通常更方便使用GHC.TypeLits版本的Nat。 如果必须在类型上实际执行类型级计算,则某些计算可以使用递归版本更轻松地完成。
由于我们只需要将自然数用作标记,因此我们可以坚持使用GHC.TypeLits解决方案。 因此,我们应该这样定义您的数据类型:
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE KindSignatures #-}
import GHC.TypeLits
data Z (n :: Nat) = El Integer

Show实例中,我们需要利用GHC.TypeLits中的其他工具将类型级别的Nat转换为值级别的Integer,以便将其包含在打印表示中。
instance (KnownNat n) => Show (Z n) where
  show el@(El e) = show e ++ " (mod " ++ show (natVal el) ++ ")"

这里有一些神奇的事情发生了!natVal函数的签名如下:
natVal :: forall n proxy. KnownNat n => proxy n -> Integer

意味着对于一个"KnownNat"(不知道是什么的)类型,它可以接受一个类型为"proxy n"的代理值,并返回与类型级别参数"n"对应的实际整数。幸运的是,我们的原始元素具有类型"Z n",非常适合"proxy n"类型模式,因此通过运行"natVal el",我们得到了与"Z n"中类型级别的"n"相对应的值级别"Integer"。
我们将在"Integral"实例中使用同样的魔法:
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)

请注意,El构造函数中的k被省略了,因为它不是数据级量。在需要时,可以使用KnownNat实例和natVal el来检索它。
完整程序如下:
{-# 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)

它按预期工作:
> :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 7In 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)

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接