Как я могу сбросить с государством в Haskell?
У меня есть простая функция (фактически используется для некоторых задач проекта Euler). Превращает список цифр в десятичное число.
fromDigits :: [Int] -> Integer
fromDigits [x] = toInteger x
fromDigits (x:xs) = (toInteger x) * 10 ^ length xs + fromDigits xs
Я понял, что тип [Int] не идеально. fromDigits должен иметь возможность принимать другие входные данные, например, последовательности, может быть, даже foldables...
Моя первая идея состояла в том, чтобы заменить вышеприведенный код на "складывание с состоянием". Какова правильная (= минимальная) категория Haskell для вышеуказанной функции?
6 ответов
Вы должны избегать использования length и напишите свою функцию, используя foldl (или же foldl'):
fromDigits :: [Int] -> Integer
fromDigits ds = foldl (\s d -> s*10 + (fromIntegral d)) 0 ds
Из этого должно быть понятно обобщение на любой Foldable.
Во-первых, сворачивание уже связано с переносом состояния. Foldable это именно то, что вы ищете, нет необходимости State или другие монады.
Во-вторых, было бы более естественно определить базовый случай в пустых списках, а затем случай для непустых списков. В настоящее время функция не определена в пустых списках (хотя она будет полностью действительной). И обратите внимание, что [x] это просто сокращение для x : [],
В текущей форме функция была бы почти выразимой, используя foldr, Однако в пределах foldl список или его части недоступны, поэтому вы не можете вычислить length xs, (Вычислительный length xs на каждом шаге также делает всю функцию излишне O (n ^ 2).) Но этого можно легко избежать, если вы переделаете процедуру, чтобы использовать список наоборот. Новая структура функции может выглядеть так:
fromDigits' :: [Int] -> Integer
fromDigits' = f 0
where
f s [] = s
f s (x:xs) = f (s + ...) xs
После этого попробуйте использовать foldl выражать f и, наконец, заменить его на Foldable.foldl,
Лучший способ решить эту проблему - составить список ваших полномочий 10. Это довольно просто, используя iterate:
powersOf :: Num a => a -> [a]
powersOf n = iterate (*n) 1
Тогда вам просто нужно умножить эти степени 10 на их соответствующие значения в списке цифр. Это легко сделать с zipWith (*), но вы должны убедиться, что это в правильном порядке в первую очередь. Это просто означает, что вы должны переупорядочить свои цифры так, чтобы они были в порядке убывания, а не в порядке возрастания:
zipWith (*) (powersOf 10) $ reverse xs
Но мы хотим вернуть Integerне Intтак что давайте через map fromIntegral там
zipWith (*) (powersOf 10) $ map fromIntegral $ reverse xs
И все, что осталось, это подвести их
fromDigits :: [Int] -> Integer
fromDigits xs = sum $ zipWith (*) (powersOf 10) $ map fromIntegral $ reverse xs
Или для фанатов без очков
fromDigits = sum . zipWith (*) (powersOf 10) . map fromIntegral . reverse
Теперь вы также можете использовать сложение, которое в основном является чистым циклом for, где функция - это тело вашего цикла, начальное значение - это, ну, в общем, начальное состояние, а список, который вы предоставляете, - это значения, по которым вы циклически выполняете, В этом случае ваше состояние является суммой и на какую власть вы опираетесь. Мы могли бы создать свой собственный тип данных, чтобы представить это, или мы могли бы просто использовать кортеж, в котором первый элемент - это текущая сумма, а второй - текущая мощность:
fromDigits xs = fst $ foldr go (0, 1) xs
where
go digit (s, power) = (s + digit * power, power * 10)
Это примерно эквивалентно коду Python
def fromDigits(digits):
def go(digit, acc):
s, power = acc
return (s + digit * power, power * 10)
state = (0, 1)
for digit in digits:
state = go(digit, state)
return state[0]
Такая простая функция может нести все свое состояние в своих голых аргументах. Возьмите аргумент аккумулятора, и операция станет тривиальной.
fromDigits :: [Int] -> Integer
fromDigits xs = fromDigitsA xs 0 # 0 is the current accumulator value
fromDigitsA [] acc = acc
fromDigitsA (x:xs) acc = fromDigitsA xs (acc * 10 + toInteger x)
Если вы хотите "свернуть с состоянием", вероятно, Traversable - это та абстракция, которую вы ищете. Одним из методов, определенных в классе Traversable, является
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
По сути, traverse принимает "функцию с состоянием" типа a -> f b и применяет его к каждой функции в контейнере t a, в результате чего в контейнере f (t b), Вот, f может быть State, и вы можете использовать траверс с функцией типа Int -> State Integer (), Это создаст бесполезную структуру данных (список единиц в вашем случае), но вы можете просто отказаться от нее. Вот решение вашей проблемы с использованием Traversable:
import Control.Monad.State
import Data.Traversable
sumDigits :: Traversable t => t Int -> Integer
sumDigits cont = snd $ runState (traverse action cont) 0
where action x = modify ((+ (fromIntegral x)) . (* 10))
test1 = sumDigits [1, 4, 5, 6]
Однако, если вам действительно не нравится создавать структуру данных, отброшенных, вы можете просто использовать Foldable с несколько хитрым Monoid реализация: хранить не только вычисленный результат, но и 10^n, где n это количество цифр, преобразованных в это значение. Эта дополнительная информация дает вам возможность объединить два значения:
import Data.Foldable
import Data.Monoid
data Digits = Digits
{ value :: Integer
, power :: Integer
}
instance Monoid Digits where
mempty = Digits 0 1
(Digits d1 p1) `mappend` (Digits d2 p2) =
Digits (d1 * p2 + d2) (p1 * p2)
sumDigitsF :: Foldable f => f Int -> Integer
sumDigitsF cont = value $ foldMap (\x -> Digits (fromIntegral x) 10) cont
test2 = sumDigitsF [0, 4, 5, 0, 3]
Я бы придерживался первой реализации. Хотя он создает ненужную структуру данных, он короче и проще для понимания (насколько понимает читатель Traversable).
Если вы действительно решили использовать правильную фолд для этого, вы можете комбинировать расчет length xs с таким расчетом (взять на себя смелость определения fromDigits [] = 0):
fromDigits xn = let (x, _) = fromDigits' xn in x where
fromDigits' [] = (0, 0)
fromDigits' (x:xn) = (toInteger x * 10 ^ l + y, l + 1) where
(y, l) = fromDigits' xn
Теперь должно быть очевидно, что это эквивалентно
fromDigits xn = fst $ foldr (\ x (y, l) -> (toInteger x * 10^l + y, l + 1)) (0, 0) xn
Шаблон добавления дополнительного компонента или результата к вашему аккумулятору и его отбрасывания после возвращения сгиба является очень общим, когда вы переписываете рекурсивные функции с использованием сгибов.
Сказав это, foldr с функцией, которая всегда строга во втором параметре, это действительно очень плохая идея (чрезмерное использование стека, возможно переполнение стека в длинных списках), и вам действительно следует написать fromDigits как foldl как некоторые другие ответы предложили.