Haskell实现求数字至回文数的迭代求和序列问题

首先，我们先明确需求：从输入的初始数字出发，每次调用invertedSum生成下一个数，将这些数依次存入列表，直到生成的数是回文数为止（这个最终的回文数也要包含在列表中）。比如你给出的例子，sumUpToCapicua 1999会生成从1999第一次调用invertedSum得到的11990开始，直到最后一个回文数712217的所有中间结果。

方案1：递归实现（最直观） #

递归是最贴合这个问题逻辑的写法——我们每次计算当前数的下一个值，判断是否是回文：如果是，就返回只包含这个值的列表；如果不是，就把这个值加入列表头部，然后递归处理这个值。

代码如下：

sumUpToCapicua :: Integer -> [Integer]
sumUpToCapicua n = go (invertedSum n)
  where
    go current = if isCapicua current
                 then [current]
                 else current : go (invertedSum current)

逻辑解释：

1. 首先用invertedSum n得到初始数的第一个迭代结果，作为递归函数go的起始输入。
2. 递归函数go接收当前数：
   • 如果当前数是回文（通过isCapicua判断），就返回只包含它的列表，终止递归。
   • 如果不是回文，就把当前数加入列表，然后递归调用go处理invertedSum current（即下一个迭代结果）。

测试你的例子：sumUpToCapicua 1999会依次生成11990、21901、32813、64636、128282、411103、712217，正好和你给出的结果一致。

方案2：使用unfoldr（更函数式的写法） #

如果你偏好更函数式的风格，可以用Data.List中的unfoldr函数来生成这个列表。unfoldr的核心是通过一个状态转换函数，逐步生成列表元素，直到返回Nothing时停止。

代码如下：

import Data.List (unfoldr)

sumUpToCapicua :: Integer -> [Integer]
sumUpToCapicua n = unfoldr step (Right (invertedSum n))
  where
    step (Right current) =
      if isCapicua current
      then Just (current, Left ())  -- 生成回文数后切换状态，下一次迭代停止
      else Just (current, Right (invertedSum current))
    step (Left ()) = Nothing

不过相比之下，递归写法更直观易懂，对于这个问题来说完全足够，而且Haskell的惰性求值会处理好长列表的情况——比如你提到的输入1000000079994144385生成长度259的列表，递归写法不会有栈溢出或者性能问题，因为Haskell的递归是惰性的，会按需生成元素。

边界情况说明 #

• 如果输入的初始数本身就是回文数，函数依然会正常工作：它会先计算invertedSum n，然后继续迭代直到得到下一个回文数，比如sumUpToCapicua 121会返回[242]（因为121+121=242，242是回文）。
• 如果迭代过程中出现循环（即某个非回文数重复出现），函数会无限递归——不过根据你的问题描述，输入1000000079994144385能终止并生成长度259的列表，说明这个输入的迭代链是终止的。

内容的提问来源于stack exchange，提问作者user9183739