Блог

Главная - Вопросы по программированию - как проверить, является ли число восьмеричным в Haskell

как проверить, является ли число восьмеричным в Haskell

#haskell #functional-programming

Вопрос:

Мне нужна программа, которая получает строку, содержащую восьмеричное число, и преобразует ее в десятичное. Если строка содержит что-либо, что не является числом от 0 до 8, функция должна вернуть 0.

Это то, что у меня есть:

 octoDec :: [Char] -> Int
octoDec [] = 0
octoDec (x:xs) = ((digitToInt(x)) * 8 ^(length xs))   octoDec xs

Если я войду octoDec ['1','2','3'] , я получу 83 то, что и ожидалось. Однако, как я могу проверить пользователя, не прибегая к другой функции?

Редактировать: мне удалось создать функцию, которая проверяет, содержит ли число только цифры от 0 до 7:

 isOcto :: [Char] -> Bool
isOcto [] = True
isOcto (x:xs) | (digitToInt(x) > 0) amp;amp; digitToInt(x) < 7 = isOcto (xs)
              |otherwise = False

чего я хотел, так это объединить эти две функции в одну и вернуть нулю значение invalid.

Комментарии:

1. Что вы подразумеваете под «необходимостью другой функции»? Вам нужно определить другую функцию верхнего уровня? Нужно использовать другую функцию? Нужно ли вообще определять какую-либо другую функцию?

2. Я хотел, чтобы проверка восьмеричности производилась в функции octoDec

3. Метод Хорнера — это более эффективный способ вычисления значения. Для n десятичного числа вам нужно всего O (n) умножений вместо O (n) операций возведения в степень.

Ответ №1:

Если вы хотите octoDec не только вернуть результат, но и определить, возможен ли вообще результат, верните a Maybe Int вместо Int :

 octoDec :: [Char] -> Maybe Int
octoDec [] = Just 0
octoDec (x:xs) = do
  rest <- octoDec xs
  let d = digitToInt x
  guard $ d >= 0 amp;amp; d <= 7 
  pure $ rest   d * 8^length xs

guard Функция from Control.Monad вернет весь do блок Nothing , если условие не выполняется.

Ответ №2:

Во-первых, вы захотите использовать метод Хорнера для эффективного преобразования последовательности цифр в одно значение.

 > foldl (acc n -> 8*acc   n) 0 (map digitToInt "123")
83

map digitToInt анализирует строку и
foldl (acc n -> 8*acc n) 0 является функцией, которая оценивает результат синтаксического анализа.

 horner :: [Int] -> Int
horner = foldl (acc n -> 8*acc   n) 0

parseString :: [Char] -> [Int]
parseString = fmap digitToInt

octoDec :: [Char] -> Int
octoDec = horner . parseString

Однако digitToInt это не совсем правильно: он может принимать цифры больше 7,

 > parseString "193"
[1,9,3]

и вызывает исключение для значения, которое вообще не является цифрой.

 > parseString "foo"
[15,*** Exception: Char.digitToInt: not a digit 'o'

Мы можем написать лучшую функцию:

 octalDigitToInt :: Char -> Maybe Int
octalDigitToInt c | c `elem` "01234567" = Just (digitToInt c)
                  | otherwise = Nothing

Мы можем использовать это для преобразования восьмеричного числа в последовательность цифр, используя traverse вместо fmap :

 parseString' :: [Char] -> Maybe [Int]
parseString' = traverse octalDigitToInt

Допустимая восьмеричная строка выдает Just значение:

 > parseString' "123"
Just [1,2,3]

в то время как недопустимые строки выдают Nothing значение:

 > parseString' "193"
Nothing
> parseString' "foo"
Nothing

(Представьте traverse себе функцию, которая не только применяет функцию к списку значений, но и выдает список результатов только в случае успешного выполнения каждого приложения. Точнее, это комбинация sequence и fmap :

 traverse f = sequence . fmap f

где sequence находится функция, которая «инвертирует» значение типа [Maybe Int] в значение типа Maybe [Int] .)

С более надежной версией parseString нам нужно адаптироваться octoDec , чтобы учесть вероятность сбоя синтаксического анализа. Мы делаем это, используя fmap для «подъема» horner в Maybe функтор.

 octoDec' :: [Char] -> Maybe Int
octoDec' s = fmap horner (parseString' s)  -- or octoDec = fmap horner . parseString'
Метки: ,