在Haskell中处理样板文件

Question

这是一个软问题,但在下面的代码中,标有"caesar ciphers"的部分有很多重复.什么是"Haskell"处理这个问题的方法？我应该提高阶函数吗？我想到了,但我不知道什么是有道理的.是否有一种"密码"类型,我可以为密码定义？

此外,我知道它可能看起来有点过度工程,因为我在两个地方做同样的错误检查,但我认为从每个功能"意味着什么"的角度来看是有意义的.建议？

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

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钥匙

• 我遵循丹尼尔关于如何bruteForceCaesar提高效率的建议.

完整的代码在这里.

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.