Как сфотографироваться в Haskell?

Question

У меня есть простая функция (используется для некоторых проблем проекта Эйлера, по сути). Он превращает список цифр в десятичное число.

fromDigits :: [Int] -> Integer 
fromDigits [x] = toInteger x 
fromDigits (x:xs) = (toInteger x) * 10^length xs + fromDigits xs 

Я понял, что тип [Int] не идеален. fromDigits должен иметь возможность принимать другие входы, например, последовательности, возможно даже foldables ...

Моя первая идея состояла в том, чтобы заменить вышеуказанный код своего рода «сгибом с состоянием». Какова правильная (= минимальная) категория Haskell для вышеуказанной функции?

Answer 1

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

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

Отсюда обобщение на любой Складная должно быть ясно.

Answer 2

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

Answer 3

Такая простая функция может нести все свое состояние в своих голых аргументах. Соберите аргумент аккумулятора, и операция станет тривиальной.

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) 

Answer 4

Лучший способ решить эту проблему, чтобы создать список ваших полномочий 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 

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

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] 

Answer 5

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

Answer 6

Если вы хотите «свернуть с состоянием», возможно, Traversable - это абстракция, которую вы ищете. Одним из методов, определенных в классе Traversable

traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 

В основном, траверс принимает «динамическую функцию» типа a -> f b и применяет его к каждой функции в контейнере t a, в результате чего в контейнере f (t b). Здесь f может быть State, и вы можете использовать траверс с функцией типа Int -> State Integer(). Это создало бы бесполезную структуру данных (список единиц в вашем случае), но вы можете просто отказаться от нее.Вот решение вашей проблемы с помощью проходимой:

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).