2

下面是一个模算数 Num 实例的实现，它以Data.Fixed.

我想编写一个替代实现，fromRational它看起来像：

fromRational r = case invertMod (denominator r) theModulus of
                   Just inv -> normalize $ (numerator r) * inv
                   Nothing -> error "..."

但我不知道我会用什么theModulus。与其他类型类函数不同，我没有Modular a可以调用的类型值modulus。

{-# LANGUAGE NoMonomorphismRestriction #-}

import Math.NumberTheory.Moduli (invertMod)
import Data.Ratio (numerator, denominator)

class HasModulus a where
  modulus :: p a -> Integer

withType :: (p a -> f a) -> f a
withType foo = foo undefined

withModulus :: (HasModulus a) => (Integer -> f a) -> f a
withModulus foo = withType (foo . modulus)

newtype Modular a = M Integer

normalize :: HasModulus a => Integer -> Modular a
normalize x = withModulus $ \m -> M (x `mod` m)

instance (HasModulus a) => Num (Modular a) where
  (M a) + (M b) = normalize (a+b)
  (M a) - (M b) = normalize (a-b)
  (M a) * (M b) = normalize (a*b)
  negate (M a)  = normalize (-a)
  abs           = id
  signum _      = fromInteger 1
  fromInteger   = normalize

instance (HasModulus a) => Fractional (Modular a) where
  recip ma@(M a) = case invertMod a (modulus ma) of
                     Just inv -> normalize $ inv
                     Nothing  -> error "divide by zero error"
  ma / mb        = ma * (recip mb)
  fromRational r = (fromInteger $ numerator r) / (fromInteger $ denominator r)

instance (HasModulus a) => Show (Modular a) where
  show mx@(M x) = (show x) ++ " mod " ++ (show $ modulus mx)

data M5 = M5
data M7 = M7

instance HasModulus M5 where modulus _ = 5
instance HasModulus M7 where modulus _ = 7

bar = 1 / 3

main = do print $ (bar :: Modular M5)
          print $ (bar :: Modular M7)
4

2 回答 2

1

一种fromRational更接近您的初始 Ansatz 的方法是

fromRational r = let x = case invertMod (denominator r) (modulus x) of
                           Just inv -> normalize $ (numerator r) * inv
                           Nothing -> error "..."
                 in x

由于结果是 类型Modular a，我们可以从中获得模数（无需检查）。所以我们只需要给它命名，这样我们就可以在需要的地方引用它。

于 2013-02-20T13:12:15.983 回答
0

我想通了...关键是使用该withModulus功能：

mdivide :: HasModulus a => Integer -> Integer -> Modular a
mdivide x y = withModulus $ M . mdiv' x y
                where mdiv' x y m =
                        case invertMod y m of
                          Just inv -> (x * inv) `mod` m
                          Nothing  -> error "..."

进而...

fromRational r = mdivide (numerator r) (denominator r)
于 2013-02-20T04:35:30.150 回答