英文:
How do I make a Mod type with a variable as a parameter?
问题
这是您的Haskell代码的部分翻译:
{-# LANGUAGE DataKinds #-}
module Cryptography.WringTwistree.Mix3
( mix
, fiboPair
, searchDir
) where
import Data.Bits
import Data.Word
import qualified Data.Sequence as Seq
import Data.Sequence ((><), (<|), (|>), Seq((:<|)), Seq((:|>)))
import Math.NumberTheory.ArithmeticFunctions
import GHC.TypeLits (Nat)
import Data.Mod
import Math.NumberTheory.Primes
mix :: (Num t, Bits t) -> t -> t -> t -> t
mix a b c = xor a mask
where mask = (a .|. b .|. c) - (a .&. b .&. c)
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)
fiboPair :: Integer -> [Integer]
fiboPair n = take 2 $ dropWhile (<= n) fibonacci
searchDir :: Integer -> (Integer, Int)
searchDir n
| r * 2 < den = (q, 1)
| otherwise = (q + 1, (-1))
where [num, den] = fiboPair (2 * n)
(q, r) = (n * num) `divMod` den
isMaxOrder :: Integral a => Nat -> a -> [a] -> a -> Bool
isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
where modln = (fromIntegral n) :: Mod modl
modl1 = 1 :: Mod modl
powns = map ((modln ^%) . (car `div`)) fac
allnot1 = foldl (&&) True (map (/= modl1) powns)
关于错误的问题,您提到参数是正整数和正整数列表,但您在函数isMaxOrder
中使用了Mod
类型。您需要确保将Mod
类型的参数限定为适当的类型。以下是可能的修改:
isMaxOrder :: Nat -> Integer -> [Integer] -> Integer -> Bool
isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
where modln = fromIntegral n :: Mod modl
modl1 = 1 :: Mod modl
powns = map ((modln ^%) . (car `div`)) fac
allnot1 = foldl (&&) True (map (/= modl1) powns)
这些更改应该有助于解决类型相关的错误。如果问题仍然存在,请提供更多上下文,以便我可以进一步帮助您解决问题。
英文:
Here's my partially written Haskell code to search for a number of maximum multiplicative order:
{-# LANGUAGE DataKinds #-}
module Cryptography.WringTwistree.Mix3
( mix
, fiboPair
, searchDir
) where
import Data.Bits
import Data.Word
import qualified Data.Sequence as Seq
import Data.Sequence ((><), (<|), (|>), Seq((:<|)), Seq((:|>)))
import Math.NumberTheory.ArithmeticFunctions
import GHC.TypeLits (Nat)
import Data.Mod
import Math.NumberTheory.Primes
mix :: (Num t,Bits t) => t -> t -> t -> t
mix a b c = xor a mask
where mask = (a .|. b .|. c) - (a .&. b .&. c)
fibonacci = 0 : 1 : zipWith (+) fibonacci (tail fibonacci)
fiboPair :: Integer -> [Integer]
fiboPair n = take 2 $ dropWhile (<= n) fibonacci
searchDir :: Integer -> (Integer,Int)
-- fst=n/φ rounded to nearest. snd=+1 or -1, indicating search direction.
-- e.g. if n=89, returns (55,1). Search 55,56,54,57,53...
-- if n=144, returns (89,(-1)). Search 89,88,90,87,91...
searchDir n
| r*2 < den = (q,1)
| otherwise = (q+1,(-1))
where [num,den] = fiboPair (2*n)
(q,r) = (n*num) `divMod` den
isMaxOrder :: Integral a => Nat -> a -> [a] -> a -> Bool
-- isMaxOrder modl car fac n
-- where modl is the modulus, car is its Carmichael function,
-- fac is the set of prime factors of car (without multiplicities),
-- and n is the number being tested.
-- Returns true if n has maximum order, which implies it's a primitive root
-- if modulus has any primitive roots.
isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
where modln = (fromIntegral n) :: Mod modl
modl1 = 1 :: Mod modl
powns = map ((modln ^%) . (car `div`)) fac
allnot1 = foldl (&&) True (map (/= modl1) powns)
I try to compile this and get these errors:
/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:43:36: error:
• Could not deduce (GHC.TypeNats.KnownNat m0)
arising from a use of ‘^%’
from the context: Integral a
bound by the type signature for:
isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
The type variable ‘m0’ is ambiguous
• In the first argument of ‘(==)’, namely ‘(modln ^% car)’
In the first argument of ‘(&&)’, namely ‘(modln ^% car) == modl1’
In the expression: (modln ^% car) == modl1 && allnot1
|
43 | isMaxOrder modl car fac n = (modln ^% car) == modl1 && allnot1
| ^^
/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:44:18: error:
• Could not deduce (GHC.TypeNats.KnownNat modl1)
arising from a use of ‘fromIntegral’
from the context: Integral a
bound by the type signature for:
isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
Possible fix:
add (GHC.TypeNats.KnownNat modl1) to the context of
an expression type signature:
forall (modl1 :: Nat). Mod modl1
• In the expression: (fromIntegral n) :: Mod modl
In an equation for ‘modln’: modln = (fromIntegral n) :: Mod modl
In an equation for ‘isMaxOrder’:
isMaxOrder modl car fac n
= (modln ^% car) == modl1 && allnot1
where
modln = (fromIntegral n) :: Mod modl
modl1 = 1 :: Mod modl
powns = map ((modln ^%) . (car `div`)) fac
allnot1 = foldl (&&) True (map (/= modl1) powns)
|
44 | where modln = (fromIntegral n) :: Mod modl
| ^^^^^^^^^^^^
/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:45:17: error:
• Could not deduce (GHC.TypeNats.KnownNat modl1)
arising from the literal ‘1’
from the context: Integral a
bound by the type signature for:
isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
Possible fix:
add (GHC.TypeNats.KnownNat modl1) to the context of
an expression type signature:
forall (modl1 :: Nat). Mod modl1
• In the expression: 1 :: Mod modl
In an equation for ‘modl1’: modl1 = 1 :: Mod modl
In an equation for ‘isMaxOrder’:
isMaxOrder modl car fac n
= (modln ^% car) == modl1 && allnot1
where
modln = (fromIntegral n) :: Mod modl
modl1 = 1 :: Mod modl
powns = map ((modln ^%) . (car `div`)) fac
allnot1 = foldl (&&) True (map (/= modl1) powns)
|
45 | modl1 = 1 :: Mod modl
| ^
/home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:46:29: error:
• Could not deduce (GHC.TypeNats.KnownNat m1)
arising from a use of ‘^%’
from the context: Integral a
bound by the type signature for:
isMaxOrder :: forall a. Integral a => Nat -> a -> [a] -> a -> Bool
at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:36:1-56
The type variable ‘m1’ is ambiguous
Relevant bindings include
powns :: [Mod m1]
(bound at /home/phma/src/wring-twistree/src/Cryptography/WringTwistree/Mix3.hs:46:9)
• In the first argument of ‘(.)’, namely ‘(modln ^%)’
In the first argument of ‘map’, namely ‘((modln ^%) . (car `div`))’
In the expression: map ((modln ^%) . (car `div`)) fac
|
46 | powns = map ((modln ^%) . (car `div`)) fac
| ^^
The parameters to isMaxOrder
are positive integers and a list of positive integers. I first tried making modl
of type a
, then tried Nat
(and importing GHC.TypeLits
unqualified resulted in a conflict of mod
or something). I can type 1 :: Mod 89
and it works, but 1 :: Mod (fromIntegral 89)
results in an error.
答案1
得分: 1
你需要 modulo
。
isMaxOrder modl car fac n = case (modulo n modl, modulo 1 modl) of
(SomeMod modln, SomeMod modl1) -> ...
你也可以在不先解包的情况下使用生成的 SomeMod
。所有通常的类型类实例都可用。
英文:
You need modulo
.
isMaxOrder modl car fac n = case (modulo n modl, modulo 1 modl) of
(SomeMod modln, SomeMod modl1) -> ...
You can also use the resulting SomeMod
s without unwrapping them first if you like. All the usual typeclass instances are available.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论