处理Haskell中的样板代码

Question

这有点抽象，但在以下代码中，“凯撒密码”部分存在大量重复。在Haskell中，应该如何处理这种情况？我应该创建一个高阶函数吗？我考虑过这个问题，但不知道哪种方式更合理。是否可以定义一个“cipher”类型来制作密码？此外，尽管可能看起来有些过度设计，但我认为在两个地方进行相同的错误检查是有意义的，因为每个函数的“意义”不同。您有什么建议吗？

import Data.Char
import Control.Applicative
import Control.Monad
import Math.NumberTheory.Powers

--Helpers

extendedGcd::Integer->Integer->(Integer, Integer)
extendedGcd a b | r == 0 = (0, 1)
                | otherwise = (y, x - (y * d))
                where
                    (d, r) = a `divMod` b
                    (x, y) = extendedGcd b r

modularInverse::Integer->Integer->Maybe Integer
modularInverse n b | relativelyPrime n b = Just . fst $ extGcd n b
                   | otherwise = Nothing
                   where
                        extGcd = extendedGcd

relativelyPrime::Integer->Integer->Bool
relativelyPrime m n = gcd m n == 1 

textToDigits::String->[Integer]
textToDigits = map (\x->toInteger (ord x - 97)) 

digitsToText::[Integer]->String
digitsToText = map (\x->chr (fromIntegral x + 97)) 

--Caesar Ciphers

caesarEncipher::Integer->Integer->Integer->Maybe Integer
caesarEncipher r s p | relativelyPrime r 26 = Just $ mod (r * p + s) 26
                     | otherwise = Nothing

caesarDecipher::Integer->Integer->Integer->Maybe Integer
caesarDecipher r s c | relativelyPrime r 26 = mod <$> ((*) <$> q <*> pure (c - s)) <*> pure 26
                     | otherwise = Nothing
    where
        q = modularInverse r 26

caesarEncipherString::Integer->Integer->String->Maybe String
caesarEncipherString r s p | relativelyPrime r 26 = fmap digitsToText $ mapM (caesarEncipher r s) plaintext
                           | otherwise = Nothing
    where
        plaintext = textToDigits p

caesarDecipherString::Integer->Integer->String->Maybe String
caesarDecipherString r s c | relativelyPrime r 26 = fmap digitsToText $ mapM (caesarDecipher r s) ciphertext
                           | otherwise = Nothing
    where
        ciphertext = textToDigits c

bruteForceCaesarDecipher::String->[Maybe String]
bruteForceCaesarDecipher c = caesarDecipherString <$> [0..25] <*> [0..25] <*> pure c

- afkbowflexin

---

旁注：凯撒密码的内容可能应该放到自己的模块中。 - Niklas B.

另外一点需要注意的是：Math.NumberTheory.GCD.extendedGCD，Math.NumberTheory.Moduli.invertMod。 - Daniel Fischer

另外一点需要注意的是：那个数论库在 hackage 上的一个包中，名为 arithmoi。 - Thomas M. DuBuisson

此外，您还可以将其作为 StreamCipher 类的实例化对象来使用 crypto-api。 - Thomas M. DuBuisson

Answer 1

定义Key类型并使用智能构造函数

主要的样板代码来源是反复检查r是否可逆，以及计算它的逆。将操作（例如encipher）分成两步：首先检查，然后实际加密，这样可以只写一次检查部分。

一种实现方法是定义一个新类型CaesarKey，该类型保证仅包含有效密钥。我们可以使用智能构造函数来保证这个不变式，如下所示:

{-# LANGUAGE RecordWildCards #-} -- for the Key{..} syntax below

-- invariant: r and q are inverses mod 26. 
-- To ensure this invariant, we only export the 'caesarKey' smart constructor,
-- and not the underlying 'Key' constructor
data CaesarKey = Key { r :: Integer, s :: Integer, q :: Integer }

caesarKey :: Integer -> Integer -> Maybe CaesarKey
caesarKey r s = Key r s <$> invertMod r 26

-- ciphers
encipher :: CaesarKey -> Integer -> Integer
encipher Key{..} p = mod (r * p + s) 26

decipher :: CaesarKey -> Integer -> Integer
decipher Key{..} c = mod (q * (c - s)) 26

encipherString :: CaesarKey -> String -> String
encipherString key = digitsToText . map (encipher key) . textToDigits

decipherString :: CaesarKey -> String -> String
decipherString key = digitsToText . map (decipher key) . textToDigits

定义对键进行反转的invert操作

现在我们可以利用丹尼尔的观察结果，即decipher只是在不同的密钥（即“逆密钥”）上定义的encipher。因此，让我们定义一个反转密钥的操作：

-- turns a key suitable for encoding into one suitable for decoding, and vice versa.
--   @invert (invert key) = key@
invert :: CaesarKey -> CaesarKey
invert (Key r s q) = Key q ((26-q)*s) r

现在，我们可以丢弃decipher和decipherString函数，因为它们是不必要的（即最好使用invert）。

编写一个allKeys函数

从概念上讲，我们可以将bruteForceCaesarDecipher分为两个任务：第一步，生成所有可能的密钥；第二步，使用每个密钥解码文本。让我们在代码中实现这个功能：

allKeys :: [CaesarKey]
allKeys = catMaybes $ caesarKey <$> [1,3..25] <*> [1,3..25]

bruteForceCaesar :: String -> [String]
bruteForceCaesar str = [encipherString key str | key <- allKeys]

除了让代码更易于理解（在我看来），按照这种方式分割代码的好处是我们只需要构建密钥列表一次，而不必为我们想要解码的每个字符串重新构建密钥。

还请注意以下几个小改动：

• 我使用了catMaybes :: [Maybe a] -> [a]来去除Nothing键。

• 我按照Daniel的建议修改了bruteForceCaesar以使其更有效率。

完整代码在此处。

- rp123

---

我仔细阅读并遵循了您的建议。这产生了令人惊奇的简洁易读的代码，并避免了我在<&>，fmap和相关操作中所做的许多花式操作。还有一件事，在allKeys声明中，第二个列表实际上应该是[1..25]，因为s不需要与26互质。非常感谢您的帮助！ - afkbowflexin

Answer 2

请注意，加密和解密使用完全相同的算法，因此您应该拥有一个执行这一操作的函数。

transform :: Integer -> Integer -> Integer -> Integer
transform mult trans n = (mult * n + trans) `mod` 26

那么每个字符都检查互质性并计算模反元素是很浪费的，因此我建议：

caesarEncipherString r s p
    | gcd r 26 == 1 = Just $ digitsToText $ map (transform r s) $ textToDigits p
    | otherwise     = Nothing

caesarDecipherString r s c = do
    mi <- modularInverse r 26
    caesarEncipherString mi (mi*(26-s)) c

针对暴力破解攻击，

bruteForceCaesarDecipher c = caesarEncipherString <$> [1, 3 .. 25] <*> [0 .. 25] <*> pure c

自所有可能密钥加密的过程与解密相同，只是顺序不同而且更简单；同时，偶数明显不互质于26。

- Daniel Fischer