Работа с шаблоном в Haskell - PullRequest
Новая
       25

Работа с шаблоном в Haskell

9 голосов
/ 02 апреля 2012

Это довольно мягкий вопрос, но в следующем коде в разделе, помеченном как «Цезарь», много дублирования.Как «Хаскель» может с этим справиться?Должен ли я сделать функцию более высокого порядка?Я думал об этом, но я не знаю, что имеет смысл.Есть ли тип «шифр», который я мог бы определить для создания шифров?

Кроме того, я знаю, что он может показаться немного чрезмерным, в том смысле, что я делаю одинаковую проверку ошибок в двух местах, ноЯ думаю, что это имеет смысл с точки зрения того, что означает каждая из функций.Предложения? 

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

Ответы [ 2 ]

15 голосов
/ 02 апреля 2012

Создайте тип Key и используйте умные конструкторы

Основным источником эталона, по-видимому, являются повторные проверки того, что r обратим, и вычисление его обратного. Имеет смысл разделить ваши операции (например, encipher) на два этапа: сначала check , затем фактически шифрование . Таким образом, вы можете написать проверочную часть только один раз.

Одним из способов достижения этого является определение нового типа 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 более эффективным.

Полный код здесь .

9 голосов
/ 02 апреля 2012

Обратите внимание, что для шифрования и дешифрования используется один и тот же алгоритм, поэтому у вас должна быть одна функция, выполняющая это. 

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.

...