haskell - 双递归地定义列表的双重无限列表

Question

上下文

我问了 patching a recursively-defined list另一天。我现在正尝试通过在 2D 列表(列表的列表)上操作来提高它的水平。

我将以帕斯卡三角形为例，例如 this beautiful one :

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...

问题

我想这样表达:

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和 col0在定义中尽可能明确，并找到一种独立定义矩阵其余部分的方法。 stub :

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 .该表达式是 [] 吗？或 (:) ？这是其参数中最短的 tail col0和 remainder . col0是无限的，它和remainder一样是空的, 即 zipWith genRow pascals (tail pascals) .那是[]或 (:) ？嗯，pascals已经被评估为 (:) ，但是(tail pascals)尚未找到 WHNF。我们已经在尝试了，所以 <<loop>> .

(很抱歉用文字拼写出来，但我真的不得不像那样在脑海中追踪它才能第一次理解它)。

出路？

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

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

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

Answer 1

这是一个更简单的 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 传递给 rowCol row col，我们仍然可以看到可以生成矩阵其余部分的初始值。

现在 pascals 可以定义如下。

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

---

截断无限矩阵的助手:

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