2

我对 Haskell 很陌生，并且正在尝试创建一种类型，该类型将代表 Integral 在某个模数上的任何实例。我在网上找到了一些示例代码并正在使用它，所以我的类型定义如下所示：

data Zn n a = Zn !a !a

大多数事情都按照我的意愿进行；我可以显示、加、减等。

instance (Integral a, Show a) => Show (Zn n a) where
   show (Zn n x) = printf "(%s mod %s)" (show (mod x n)) (show n)

instance (Integral a, Reifies n a) => Num (Zn n a) where
  Zn n x + Zn _ y = Zn n (mod (x + y) n)
  Zn n x - Zn _ y = Zn n (mod (x - y) n)
  Zn n x * Zn _ y = Zn n (mod (x * y) n)
  negate (Zn n x) = Zn n (n - x)
  abs = id
  signum x@(Zn _ 0) = x
  signum (Zn n _) = Zn n 1
  fromInteger x = Zn n (mod (fromInteger x) n)
    where n = reflect (Proxy :: Proxy n)


znToIntegral :: Integral a => Zn n a -> a
znToIntegral (Zn n x) = fromIntegral x

但是，我无法显示这些类型的算术运算结果。例如，在 GHCi 中：

*Main> let x = Zn 5 3
*Main> x
(3 mod 5)
*Main> let y = Zn 5 7
(2 mod 5)
*Main> let z = x + y
*Main> z
<interactive>:6:1:
    No instance for (Integral a0) arising from a use of ‘print’
    The type variable ‘a0’ is ambiguous
    Note: there are several potential instances:
      instance Integral GHC.Int.Int16 -- Defined in ‘GHC.Int’
      instance Integral GHC.Int.Int32 -- Defined in ‘GHC.Int’
      instance Integral GHC.Int.Int64 -- Defined in ‘GHC.Int’
      ...plus 9 others
    In a stmt of an interactive GHCi command: print it

我发现这个问题在我尝试实现这些数字的许多其他方式中出现，并且了解 Data.Reflection 包的工作方式给我带来了一些麻烦。我也会对其他人似乎更自然的任何其他实现感到好奇。我最初尝试做类似的事情

newtype Zn n a = Zn a

并切换，因为我认为它会简化事情，它并没有特别。干杯!

4

2 回答 2

2

在此特定示例中，Zn是内部实现细节，不应用于构造数字。理想情况下，Zn甚至不应该从库中导出。相反，我们应该构造 usingfromInteger和 numeric 文字。

模数是fromInteger通过反射引入的，出于性能原因，我们仅将其存储在其中Zn以避免进一步使用reflect（尽管我认为reflect默认情况下没有太多开销，因此我们可能不会从该方案中获得太多收益）。如果我们只使用fromInteger创建新Zn的 -s，则模数将在整个计算中与Reifies约束一致。另一方面，如果我们手动将模数插入Zn，那么该部分Zn将始终具有该模数，并且reify（我们提供隐式配置的方式）根本不会影响它。换句话说，它弄乱了我们假定的不变量。

示例使用：

foo :: (Integral a, Reifies s a) => Zn s a -> Zn s a -> Zn s a
foo a b = e where
  c = 123
  d = a * b - 3
  e = negate (d + c)

showAFooResult = reify 12 (\(Proxy :: Proxy s) -> show (foo 3 4 :: Zn s Int))
-- fooResult == "(0 mod 12)"

在foo我们12使用reify.

如果我们眯起眼睛，foo这只是一个函数，它需要一个额外的Integral参数，它在内部用作模数。我们可以使用中的索引reify来提供参数。sProxy

如果我们不提供任何值来插入这个Reifies洞，那么我们就无法取出一个值。当然我们不能打印它，就像我们不能打印一个函数一样。

我们可以打印Zn 5 5，因为它有 type Num a => Zn n a，所以我们没有要填充的洞。另一方面，Zn 5 5 + Zn 5 5有 type (Integral a, Reifies n a) => Zn n a，因为我们Reifies n a在实例中指定了约束Num，当然+需要一个Num实例的使用。在这里，我们必须使用reify（或调用它的其他辅助函数）来提取结果。

于 2015-07-15T21:02:57.927 回答
2

为了比较，这是一个不存储模数并始终使用的实现reflect：

{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE RankNTypes #-}

import Data.Reflection
import Data.Proxy
import Text.Printf

newtype Zn a s = Zn { getZ :: a }

instance (Integral a, Show a, Reifies s a) => Show (Zn a s) where
       show x = 
           let 
               p = reflect (Proxy::Proxy s)           
           in
               printf "(%s mod %s)" (show (mod (getZ x) p)) (show p)

instance (Integral a, Reifies s a) => Num (Zn a s) where
      Zn x + Zn y = Zn (mod (x + y) (reflect (Proxy::Proxy s)))
      Zn x - Zn y = Zn (mod (x - y) (reflect (Proxy::Proxy s)))
      Zn x * Zn y = Zn (mod (x * y) (reflect (Proxy::Proxy s)))
      negate (Zn x) = Zn ((reflect (Proxy::Proxy s)) - x)
      abs = id
      signum x@(Zn 0) = x
      signum _ = Zn 1
      fromInteger x = Zn (mod (fromInteger x) p)
            where p = reflect (Proxy :: Proxy s)

一些辅助功能：

znToIntegral :: Integral a => Zn a s -> a
znToIntegral (Zn x) = fromIntegral x

-- Convince the compiler that the phantom type in the proxy
-- is the same as the one in the Zn
likeProxy :: Proxy s -> Zn a s -> Zn a s
likeProxy _ = id

withZn :: Integral a => a -> (forall s. Reifies s a => Zn a s) -> a
withZn p z = reify p $ \proxy -> znToIntegral . likeProxy proxy $ z

使用示例：

main :: IO ()
main = print $ withZn (7::Int) (Zn 3 + Zn 5)

withZn也来自 ghci。

于 2015-07-15T22:29:25.567 回答