Проверка правильности пароля - Haskell против процедурного языка

Question

Я реализовал функцию в Python, которая проверяет, достаточно ли достаточно пароля. Пароль достаточно силен, если он проходит 3 из 5 проверок. Это функция Python:

def is_valid(password): 
    checks = { 
     lambda x : True : 10, 
     lambda x : x.isupper() : 2, 
     lambda x : x.islower() : 2, 
     lambda x : x.isdigit() : 2, 
     lambda x : x in frozenset("~!@#$%^&*()-=_+[]{}<>?/\\`") : 2, 
    } 

    for c in password: 
     for func in list(checks): 
      if func(c): 
       checks[func] -= 1 
       if checks[func] == 0: 
        del checks[func] 

     if len(checks) <= 2: 
      return True 

    return False 

Эта функция может работать с бесконечным паролем, если она достаточно сильна. Если это не так, то функция будет висеть:

>>> is_valid(itertools.cycle("!!xxxxxxxx")) 
True 
>>> is_valid(itertools.cycle("UUxxxxxxxx")) 
True 

Я woundered, если бы я мог реализовать ту же функцию в Haskell более элегантно, поэтому я пришел к этому решению:

isValid :: String -> Bool 
isValid password = 
    let 
    checks = atLeast 10 password:map containsChars [isUpper, isLower, isSpecialChar, isDigit] 
    in atLeast 3 $ filter (==True) checks 
    where 
    containsChars predicate = length (take 2 $ filter predicate password) == 2 
    isSpecialChar c = isPunctuation c || isSymbol c 
    atLeast n seq = length (take n seq) == n 

Этот решение кажется немного более элегантным, но имеет недостаток в процедурных решениях. Если пароль бесконечен и не имеет достаточное количество символов в верхнем регистре, функция будет висеть, даже если она проходит другие условия:

*Main Data.Char> isValid (cycle "UUxxxxxxxx") 
True 
*Main Data.Char> isValid (cycle "!!xxxxxxxx") 
-- hangs 

есть способ реализовать элегантный soultion в Haskell, который не имеет этот недостаток ?

BTW: Есть ли что-то встроенное в Haskell, которое я могу использовать вместо функции atLeast, которую я реализовал?

Answer 1

Вы правы: если пароль уже известен, он все равно попытается установить другие условия. Поэтому я хотел бы сделать это по-другому:

check passwd = go criteria passwd 
    where 
     criteria = [(10, const True), (2, isUpper), (2, isLower), (2, isDigit), (2, isSpecial)] 
     -- password is ok if at least 3 criteria have counted down to 0 
     ok = (>=3) . length . filter (==0) . map fst 
     go crit pwd 
     | ok crit = True 
     | null pwd = False 
     | otherwise = go (map (trans (head pwd)) crit) (tail pwd) 
     trans ch (0, p) = (0, p) 
     trans ch (n, p) = if p c then (n-1, p) else (n, p) 

Идея заключается в том, чтобы проверить каждый символ, если список критериев указывает на то, что PASSWD нормально и вернуться Правда в этом случае. Затем проверьте, был ли достигнут конец пароля, в этом случае пароль недействителен. И в противном случае мы еще не установили все необходимые критерии, но имеем непустую passwd. Следовательно, мы преобразуем список критериев, применяя все функции, где счетчик еще не равен 0 текущему символу, уменьшению количества успехов и рекурсии.

Обратите внимание, что (10, const True) кодирует условие: «Passwd имеет длину не менее 10 символов».

Answer 2

Немного более эффективная версия вашей atLeast функции является inBounds функция от Data.Edison.Seq.ListSeq:

inBounds i xs 
    | i >= 0 = not (null (drop i xs)) 
    | otherwise = False 

Answer 3

Проверьте это. Идея состоит в том, чтобы иметь бесконечный список успешных проверок на данный момент. импорт Data.Char

isValid password = let 
    checks      = [isUpper, isLower, isSpecialChar, isDigit] 
    isSpecialChar c    = isPunctuation c || isSymbol c 
    toInt b      = if b then 1 else 0 
    check c      = map toInt $ map ($c) checks 
    tests      = zip [1..] $ map check password 
    accum passed ((len,t):ts) = (len,result):accum result ts where result = zipWith (+) passed t 
    accum _ []     = [] 
    valid (len,test)   = toInt (len > 10) + (length $ filter (>=2) test) >= 3 
    in any valid $ accum (repeat 0) tests 

Answer 4

Просто для удовольствия, я думал, что сталкивать очень разные ответы на другие. Идея, которую я имел, - определить моноид, который отслеживает статистику о пароле, и монотонную проверку того моноида, что пароль действителен. Во-первых, некоторые отборочные:

{-# LANGUAGE GeneralizedNewtypeDeriving, StandaloneDeriving #-} 
import Data.Char 
import Data.Monoid 
import Data.Universe 
deriving instance Num a => Num (Sum a) -- this should really be in base 

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

data Bucket = Char | Upper | Lower | Digit | Punctuation 
    deriving (Eq, Ord, Show, Read, Bounded, Enum) 
instance Universe Bucket 

type Natural = Integer -- lol, let's just pretend, okay? 
type Statistic = Bucket -> Sum Natural 

Monoid экземпляр для Statistic добавляет счетчики в каждом ведре. Теперь, чтобы подключить тип данных Bucket к более чистому миру FP, у нас будет переводчик, чтобы перейти от наших «EDSL» к функциям Haskell.

interpret :: Bucket -> (Char -> Bool) 
interpret Char = const True 
interpret Upper = isUpper 
interpret Lower = isLower 
interpret Digit = isDigit 
interpret Punctuation = isPunctuation 

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

statistic :: Char -> Statistic 
statistic c b = fromIntegral . fromEnum . interpret b $ c 

До здесь, ни один из кода на самом деле не было много «бизнес-логики» в нем - то есть, именно то, сколько символов в каждом ведре мы хотим иметь или сколько ведер мы хотим заполнить. Итак, давайте запишем эти две вещи. Первое мы просто напишем как статистику. Проверка того, что мы заполняем достаточно ведер, немного сложна, поэтому она заслуживает некоторого объяснения. Идея состоит в том, чтобы перебирать все ведра и оставлять токен, если ведро «заполнено», сравнивая его с порогами. Если мы получим достаточно токенов, статистика действительна.

thresholds :: Statistic 
thresholds Char = 10 
thresholds _ = 2 

validStatistic :: Statistic -> Bool 
validStatistic f = length [() | b <- universe, f b >= thresholds b] >= 3 

Существует насущная собственность, удерживаемая validStatistic, что не отражается в системе типа. Существует много разных способов описания этого свойства; одним из способов является наблюдение, что validStatistic f < validStatistic (f <> g) независимо от того, что f и g (все еще притворяются, что нет отрицательных чисел). На английском языке это будет означать для нас, что если какая-либо подстрока пароля действительна, то и весь пароль также действителен.

Прохладный. Теперь у нас есть все части, которые нам нужны, чтобы проверить, действительно ли пароль. Что мы сделаем, так это превратить каждый символ пароля в статистику; конгломерат всех статистических данных, когда мы идем; и проверяет, когда статистика когда-либо пересекает пороговое значение от недействительного до действительного (отмечая, что если он это сделает, он никогда не перейдет обратно к недопустимому из-за критического свойства выше).

validPassword :: String -> Bool 
validPassword = any validStatistic . scanl (<>) mempty . map statistic 

Попробуйте в GHCI:

*Main> validPassword (cycle "UUxxxxxxx") 
True 
*Main> validPassword (cycle "!!xxxxxxx") 
True 
*Main> validPassword "!!xxxxxxx" 
False 
*Main> validPassword "!!xxxxxxxx" 
True 

P.S. Вы заметили, что validPassword в основном реализованы так же, как и сокращение карты? (map statistic это карта часть; scanl (<>) mempty может быть foldr (<>) mempty вместо это уменьшить часть, any validStatistic станет validStatistic при использовании с foldr и является частью пост-обработки) делает его легко увидеть, как распараллелить вычисления validPassword в случае, если действительно есть пароли 100 МБ. ;-)

Answer 5

Вы можете использовать Моноиды или монаду:

data Pass a = NotPass | TryPass Int | Pass a deriving Show 

instance Monad Pass where 
    return = Pass 
    fail = NotPass 
    NotPass  >>= _  = NotPass 
    Pass k  >>= f  = f k 
    (TryPass a k) >>= f = case f k of 
       NotPass -> if (a < 0) NotPass else TryPass (a-1) 
       TryPass b -> TryPass b 
       Pass _ -> TryPass a 

is_valid :: String -> Bool 
is_valid password = toBool $ do 
    TryPass 3 
    toPass isUpper 
    toPass isLower 
    toPass isSpecialChar 
    toPass isDigit 
    where 
    toPass bf = unless (bf bassword) NotPass 
    toBool NotPass = false 
    toBool _  = true