Context

我问的是修补递归定义的列表 https://stackoverflow.com/q/53988970/12274另一天。我现在尝试通过在 2D 列表（列表的列表）上操作来将其提升一个级别。

我将使用帕斯卡三角形作为示例，例如这个美丽的 https://stackoverflow.com/a/27233941/12274:

pascals = repeat 1 : map (scanl1 (+)) pascals
[1,1,1,1,1,1...
[1,2,3,4,5...
[1,3,6,10...
[1,4,10...
[1,5...
[1...

Question

我想这样表达：

1. 我将提供自己的第一行和第一列（上面的示例假设第一行是repeat 1，这是足够可修复的，第一列是repeat (head (head pascals))，这会更加棘手）

2. 每个元素仍然是上面的元素和它左边的元素的函数。

3. 总的来说，它本身就是一个函数，足以使其能够在定义中插入修补函数并让它传播修补程序。

所以从外面看，我想找一个f函数这样我就可以定义pascal像这样：

pascal p = p (f pascal)

...以便pascal id与示例中的相同，并且pascal (patch (1,3) to 16)产生类似：

[1,1,1,1, 1,1...
[1,2,3,16,17...
[1,3,6,22...
[1,4,10...
[1,5...
[1...

我在哪里

让我们首先定义并提取第一行和第一列，这样我们就可以使用它们并且不会滥用它们的内容。

element0 = 1
row0 = element0 : repeat 1
col0 = element0 : repeat 1

更新要使用的定义row0很容易：

pascals = row0 : map (scanl1 (+)) pascals

但第一栏仍然是element0。更新以获取它们col0:

pascals = row0 : zipWith newRow (tail col0) pascals
  where
    newRow leftMost prevRow = scanl (+) leftMost (tail prevRow)

现在我们已经满足了第一个要求（自定义第一行和第一列）。在没有打补丁的情况下，第二个仍然很好。

我们甚至得到了第三个元素的一部分：如果我们修补一个元素，它就会向下传播，因为newRow定义为prevRow。但它不会向右传播，因为(+)运行于scanl的内部累加器，并从leftMost，在这种情况下这是一个明确的。

我尝试过的

从这里开始，正确的做法似乎是真正分离关注点。我们想要我们的初始化器row0 and col0定义中尽可能明确，并找到一种独立定义矩阵其余部分的方法。存根：

pascals = row0 : zipWith (:) (tail col0) remainder
[1,1,1,1,1,1,1,1,1,1...
[1,/-------------------
[1,|
[1,|
[1,|
[1,|  remainder
[1,|
[1,|
[1,|
[1,|

然后我们希望余数直接根据整体定义。自然的定义是：

remainder = zipWith genRow pascals (tail pascals)
  where genRow prev cur = zipWith (+) (tail prev) cur
[1,1,1,1,1,1,1,1,1,1...
<<loop>>

第一行结果很好。为什么要循环？遵循评估有助于：pascals被定义为缺点，其汽车很好（并打印）。 cdr是什么？它是zipWith (:) (tail col0) remainder。这个表达式是一个[] or (:)？这是最短的参数tail col0 and remainder. col0是无限的，它就像空一样remainder, i.e. zipWith genRow pascals (tail pascals)。就是它[] or (:)？出色地，pascals已经被评估为(:), but (tail pascals)尚未找到 WHNF。我们已经在尝试了，所以<<loop>>.

（抱歉用文字把它拼出来，但我真的必须在脑海中像这样跟踪它才能第一次理解它）。

Way out?

根据我的定义，似乎所有定义都是正确的、数据流方面的。现在循环看起来很简单，因为评估器无法确定生成的结构是否是有限的。我找不到一种方法来保证“它是无限的”。

我觉得我需要一些惰性匹配的逆向：一些惰性返回，我可以告诉评估者 WHNF 的结果为(:)，但是稍后您仍然需要调用这个 thunk 来了解其中的内容。

它仍然感觉像是一个固定点，但我还没有设法以一种有效的方式表达。

这是一个懒惰的版本zipWith这使得你的例子富有成效。它假设第二个列表至少与第一个列表一样长，但不强制这样做。

zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith' f (i : is) ~(j : js) = f i j : zipWith' f is js

-- equivalently --

zipWith' f (i : is) jjs = f i (head j) : zipWith' f is (tail js)

看看我们要定义的矩阵：

matrix =
  [1,1,1,1,1,1,1...
  [1,/-------------
  [1,|
  [1,|  remainder
  [1,|
  ...

矩阵和余数之间有一个简单的关系，它描述了这样一个事实：余数中的每个条目都是通过将其左侧的条目与其上方的条目相加而获得的：对不包括第一行的矩阵求和，然后将没有第一列的矩阵。

remainder = (zipWith . zipWith) (+) (tail matrix) (map tail matrix)

从那里，我们可以对其余部分应用修补/填充函数，以填充第一行和第一列，并编辑任何元素。这些修改将通过递归发生反馈matrix。这导致以下广义定义pascals:

-- parameterized by the patch
-- and the operation to generate each entry from its older neighbors
pascals_ :: ([[a]] -> [[a]]) -> (a -> a -> a) -> [[a]]
pascals_ pad (+) = self where
  self = pad ((zipWith . zipWith) (+) (tail self) (map tail self))

例如，最简单的填充函数是用初始行和列来完成矩阵。

rowCol :: [a] -> [a] -> [[a]] -> [[a]]
rowCol row col remainder = row : zipWith' (:) col remainder

这里我们必须小心，不要在剩余部分中偷懒，因为我们正在定义它，因此使用zipWith'上面定义的。换句话说，我们必须确保如果我们通过undefined to rowCol row col我们仍然可以看到可以生成矩阵其余部分的初始值。

Now pascals可以定义如下。

pascals :: [[Integer]]
pascals = pascals_ (rowCol (repeat 1) (repeat 1)) (+)

截断无限矩阵的助手：

trunc :: [[Integer]] -> [[Integer]]
trunc = map (take 10) . take 10