2

我有一个简单的功能（实际上用于欧拉项目的一些问题）。它将数字列表转换为十进制数。

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

我意识到这种类型[Int]并不理想。fromDigits应该能够接受其他输入，例如序列，甚至可能foldables......

我的第一个想法是用一种“带状态的折叠”替换上面的代码。上述函数的正确（= 最小）Haskell 类别是什么？

4

6 回答 6

7

首先，折叠已经是关于携带一些状态。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

之后，尝试使用foldlto expressf并最终将其替换为Foldable.foldl.

于 2014-10-15T19:25:10.760 回答
3

您应该避免使用（或）length来编写函数：foldlfoldl'

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

从这个概括到任何可折叠的东西应该是清楚的。

于 2014-10-15T19:25:41.587 回答
1

解决这个问题的更好方法是建立一个 10 次幂的列表。这很简单，使用iterate：

powersOf :: Num a => a -> [a]
powersOf n = iterate (*n) 1

然后，您只需将这些 10 的幂乘以它们在数字列表中的各自值。使用 很容易做到这一点zipWith (*)，但您必须首先确保它的顺序正确。这基本上只是意味着您应该重新排序您的数字，以便它们按数量级降序而不是升序：

zipWith (*) (powersOf 10) $ reverse xs

但我们希望它返回一个Integer, not ,所以Int让我们通过 amap 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]
于 2014-10-15T19:27:34.013 回答
0

如果你想“折叠状态”，可能 Traversable 是你正在寻找的抽象。Traversable 类中定义的方法之一是

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

基本上， traverse 采用类型的“有状态函数”a -> f b并将其应用于容器中的每个函数t a，从而产生一个容器f (t b)。在这里，fcan be State，您可以使用带有 type 函数的 traverse 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）。

于 2014-10-15T19:34:55.553 回答
0

如果您真的决定为此使用正确的折叠，您可以将计算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其他一些答案一样写成建议。

于 2014-10-15T19:34:01.173 回答
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)
于 2014-10-15T19:27:00.080 回答