Как я могу свернуть с состоянием в Haskell?

Вам следует избегать использования length и писать свою функцию, используя foldl (или foldl'):

fromDigits :: [Int] -> Integer
fromDigits ds = foldl (\s d -> s*10 + (fromIntegral d)) 0 ds

Из этого должно быть понятно обобщение на любой складной.

Во-первых, фолд — это уже перенос некоторого состояния. 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

Теперь вы также можете использовать fold, который в основном представляет собой чистый цикл 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)

Если вы действительно настроены использовать для этого правильную кратность, вы можете комбинировать вычисление 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 как некоторые из предложены другие ответы.

Если вы хотите «свернуться с состоянием», вероятно, 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).