Количество нечетных цифр в целых числах Haskell

Question

Я пытаюсь создать программу, которая подсчитывает количество нечетных цифр в целых числах, используя Haskell. Я столкнулся с проблемой проверки длинных целых чисел. Моя программа выглядит следующим образом:

oddDigits:: Integer -> Int
x = 0
oddDigits i
   | i `elem` [1,3,5,7,9] = x + 1
   | otherwise = x + 0

Если мое целое число, например, 22334455, моя программа должна вернуть значение 4, потому что в этом целом числе 4 нечетные цифры. Как я могу проверить все числа в этом целом числе? В настоящее время он только проверяет первый di git и возвращает 1 или 0. Я все еще довольно плохо знаком с haskell.

Answer 1

Вы можете сначала преобразовать целое число 22334455 в список "22334455". Затем найдите все элементы, удовлетворяющие требованию.

import Data.List(intersect)

oddDigits = length . (`intersect` "13579") . show

Answer 2

Чтобы решить такие проблемы, вы обычно делите это на более мелкие проблемы. Типичным конвейером будет:

1. разделить число в списке цифр;
2. отфильтровать нечетные цифры; и
3. посчитайте длину полученного списка.

Таким образом, вы можете реализовать / использовать вспомогательные функции. Например, мы можем сгенерировать список цифр с помощью:

digits' :: Integral i => i -> [i]
digits' 0 = []
digits' n = r : digits' q
    where (q, r) = quotRem n 10

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

Answer 3

Вот эффективный способ сделать это:

oddDigits :: Integer -> Int
oddDigits = go 0
  where
    go :: Int -> Integer -> Int
    go s 0 = s
    go s n = s `seq` go (s + fromInteger r `mod` 2) q
      where (q, r) = n `quotRem` 10

Это хвостовой рекурсив, не накапливает thunks и не создает ненужные списки или другие структуры, которые нужно будет собирать мусором. Он также правильно обрабатывает отрицательные числа.