Haskell递归优化：无需追加0实现列表末尾额外递归步骤

嘿，我完全懂你的困扰——用xs ++ [0]虽然能达到模拟末尾加0的效果，但每次都会额外创建一个新列表，对于大列表来说不仅浪费内存，还会拖慢执行效率。咱们来重构一下这个函数，不用实际拼接列表就能实现同样的逻辑。

首先，先拆解原函数的核心逻辑：这看起来是经典的柱状图最大面积问题，go函数用栈来维护递增的柱子索引和高度，当遇到比栈顶矮的柱子时，就计算栈顶柱子能扩展的最大面积。原代码里xs ++ [0]的作用是触发最后一批柱子的面积计算（因为0比所有柱子都矮，能把栈里剩下的元素全部弹出计算）。

那我们可以把“模拟末尾0”的逻辑直接整合到递归的终止条件里，不用额外拼接列表。这里有个清晰的实现方案：

rect xs = maximum $ go 0 [] xs where
  -- 正常处理列表中的每个元素
  go i s (h:hs) = case s of
    -- 当前柱子比栈顶矮，弹出栈顶计算面积，继续比较
    ((_, tH):r@((t,_):_)) | h < tH -> tH * (i - t - 1) : go i r (h:hs)
    -- 当前柱子更高，压入栈，继续处理下一个元素
    _ -> go (i + 1) ((i, h):s) hs
  
  -- 列表处理完了，模拟遇到0的情况，清空栈中剩余元素
  go i s [] = processRemainingStack i s
  
  -- 专门处理栈中剩余元素的辅助函数，相当于用0作为最后一个柱子触发计算
  processRemainingStack _ [] = []
  processRemainingStack i ((_, tH):r@((t,_):_)) = 
    tH * (i - t - 1) : processRemainingStack i r
  -- 栈里只剩最后一个元素时，宽度就是当前索引i（从0到i-1共i个位置）
  processRemainingStack i [(_, tH)] = [tH * i]

为什么这个方案更好？ #

• 效率更高：原代码的xs ++ [0]需要遍历整个xs创建新列表，时间复杂度是O(n)；而新方案直接在递归终止时处理栈，没有额外的列表创建，空间和时间效率都更优。
• 逻辑更清晰：把“处理正常元素”和“处理末尾剩余栈”的逻辑拆分，代码可读性更强，也更容易维护。
• 效果完全一致：processRemainingStack的逻辑和原代码中xs ++ [0]触发的计算完全相同，能保证结果和原函数一致。

如果想更紧凑一点，也可以把辅助函数合并到go里，不用单独写processRemainingStack：

rect xs = maximum $ go 0 [] xs where
  go i s (h:hs) = case s of
    ((_, tH):r@((t,_):_)) | h < tH -> tH * (i - t - 1) : go i r (h:hs)
    _ -> go (i + 1) ((i, h):s) hs
  go i [] [] = []
  go i ((_, tH):r@((t,_):_)) [] = tH * (i - t - 1) : go i r []
  go i [(_, tH)] [] = [tH * i]

这个版本把终止条件直接写在go里，代码更短，但可读性稍微弱一点，你可以根据自己的偏好选择。

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