一句话：为 Bird 的列表自底向上计算算法给出形式推导，并揭示其依赖的 Pascal 三角对角线性质。
某些自顶向下的问题规约在直接执行时会反复计算相同子问题。为支持自底向上算法，需要将子问题的解存入表格复用，但表格的表示与高效维护往往并不简单。本文研究一个特殊情形：函数 h 以列表为输入，且 h xs 由 xs 的所有直接子列表定义。Bird 在 2008 年给出过一个简洁但晦涩的算法，本文重新给出清晰的推导，并发现使该算法成立的关键性质。所导出的算法构造具有特定形状的树，其左脊上的大小对应 Pascal 三角中某条对角线的前缀；核心函数则把一条对角线变换到下一条。
Abstract Some top-down problem specifications, if executed, may compute sub-problems repeatedly. Instead, we may want a bottom-up algorithm that stores solutions of sub-problems in a table to be reused. How the table can be represented and efficiently maintained, however, can be tricky. We study a special case: computing a function ${\mathit{h}}$ taking lists as inputs such that ${\mathit{h}\;\mathit{xs}}$ is defined in terms of all immediate sublists of ${\mathit{xs}}$ . Richard Bird studied this problem in 2008 and presented a concise but cryptic algorithm without much explanation. We give this algorithm a proper derivation and discovered a key property that allows it to work. The algorithm builds trees that have certain shapes—the sizes along the left spine is a prefix of a diagonal in Pascal’s triangle. The crucial function we derive transforms one diagonal to the next.