访问返回值的虚拟类型

Question

下面是一个模仿Data.Fixed的模块化算术Num实例的实现。

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

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

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

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

Answer 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类型的，所以我们可以从它获得模量(不需要检查它)。所以我们所需要的就是给它命名，这样我们就可以在需要的地方引用它。

Answer 2

我想通了..。关键是使用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)