双递归定义列表的双重无限列表 [英] Birecursively defining a doubly infinite list of lists

问题描述

前几天我问了修补递归定义的列表.我现在正尝试通过对2D列表(列表列表)进行操作来将其升级.

I asked about patching a recursively-defined list the other day. I'm now trying to bring it up a level by operating on a 2D list instead (a list of lists).

我将以Pascal三角形为例，例如这个漂亮的:

I'll use Pascal's triangle as an example, like for example 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...

问题

我想这样表达:

Question

I'd like to express it such that:

1. 我将拥有自己的第一行和第一列(上面的示例假定第一行是repeat 1，可以固定，而第一列是repeat (head (head pascals))，这将更加棘手)

1. I'll come with my own first rows and columns (example above assumes first row is repeat 1, which is fixable enough, and that first column is repeat (head (head pascals)), which is going to be more tricky)

每个元素仍然是上方元素和左侧元素的函数.

Each element remains a function of the one above and the one left of it.

作为一个整体，它本身就是一个功能，足以在定义中插入补丁功能并传播补丁.

As a whole, it is a function of itself enough for it to be possible to insert a patching function in the definition and have it propagate patches.

因此，从外面，我想找到一个f函数，以便可以这样定义pascal:

So from the outside, I'd like to find an f function such that I can define pascal as such:

pascal p = p (f pascal)

...使得pascal id与示例中的相同，并且pascal (patch (1,3) to 16)产生类似以下内容:

...so that pascal id is the same as in the example, and pascal (patch (1,3) to 16) yields something like:

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

我在哪里

让我们首先定义并提取第一行和第一列，以便我们可以使用它们，而又不会试图滥用它们的内容.

Where I'm at

Let's first define and extract the first row and column, so we can have them available and not be tempted to abuse their contents.

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

更新定义以使用row0很容易:

Updating the definition to use row0 is easy enough:

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

但是第一列仍然是element0.正在将它们从col0删除:

But the first column is still element0. Updating to take them from col0:

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

现在，我们满足第一个要求(自定义第一行和第一列).没有补丁，第二个还是不错的.

Now we're good with the first requirement (custom first row and column). With no patching, the second is still good.

我们甚至获得了第三部分的一部分:如果我们修补元素，由于newRow是根据prevRow定义的，因此它将向下传播.但是它不会向右传播，因为(+)在scanl的内部累加器上操作，并且在leftMost上操作，在这种情况下是明确的.

We even get part of the third: if we patch an element, it will propagate downwards since newRow is defined in terms of prevRow. But it won't propagate rightwards, since the (+) operates on scanl's internal accumulator, and from leftMost, which is an explicit in this context.

从那里看来，正确的做法似乎是真正分离关注点.我们希望我们的初始化器row0和col0在定义中尽可能明确，并找到一种方法来独立定义矩阵的其余部分.存根:

From there, it seems like the right way to do is to really separate concerns. We want our initializers row0 and col0 as explicit as possible in the definition, and find a way to define the rest of the matrix independently. 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,|

，然后我们希望直接根据整体定义余数.自然的定义是:

and then we'd want the remainder defined directly in terms of the whole. The natural definition would be:

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)一样为null.是[]还是(:)?好的，pascals已经被评估为(:)，但是尚未找到(tail pascals).而且我们已经在尝试中，所以<<loop>>.

The first row comes out fine. Why the loop? Following the evaluation helps: pascals is defined as a cons, whose car is fine (and printed). What's is cdr? It's zipWith (:) (tail col0) remainder. Is that expression a [] or (:)? It's the shortest of its arguments tail col0 and remainder. col0 being infinite, it's as null as remainder, i.e. zipWith genRow pascals (tail pascals). Is that [] or (:)? Well, pascals has already been evaluated to (:), but (tail pascals) hasn't been found a WHNF yet. And we're already in the process of trying, so <<loop>>.

(很抱歉用单词将其拼写出来，但是我真的必须像这样在心理上追踪它，以便第一次理解它.)

(Sorry for spelling it out with words, but I really had to mentally trace it like that to understand it the first time).

根据我所定义的定义，似乎所有定义都是正确的，在数据​​流方面是明智的.现在看来循环很简单，因为评估者无法确定所生成的结构是否有限.我找不到一种方法来兑现无限好"的承诺.

With the definitions I'm at, it seems like all definitions are proper, data-flow wise. The loop now seems simply because the evaluator can't decide whether the generated structure is finite or not. I can't find a way to make it a promise "it's infinite all right".

我感觉我需要一些懒惰匹配的话题:一些懒惰的返回，我可以告诉评估者WHNF的结果是(:)，但是您仍然需要稍后再调用此thunk来找出其中的内容它.

I feel like I need some converse of lazy matching: some lazy returning where I can tell the evaluator the WHNF of this comes out as (:), but you'll still need to call this thunk later to find out what's in it.

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

It also still feels like a fixed point, but I haven't managed to express in a way that worked.

推荐答案

以下是zipWith的默认版本，可提高您的示例的工作效率.它假定第二个列表至少与第一个列表一样长，而不会强迫它.

Here's a lazier version of zipWith that makes your example productive. It assumes the second list is at least as long as the first, without forcing it.

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)

---

查看我们要定义的矩阵:

---

Looking at the matrix we want to define:

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

矩阵与余数之间存在一种简单的关系，它描述了一个事实，即余数中的每个条目都是通过将其左侧的条目与上方的条目相加而获得的:取矩阵的和而不包含其第一行，以及没有第一列的矩阵.

There is a simple relationship between the matrix and the remainder, that describes the fact that each entry in the remainder is obtained by summing the entry to its left and the one above it: take the sum of the matrix without its first row, and the matrix without its first column.

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

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

From there, we can apply a patch/padding function to the remainder, to fill in the first row and first column, and edit whatever elements. Those modifications will be fed back through the recursive occurences of matrix. This leads to the following generalized definition of 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))

例如，最简单的填充功能是使用初始行和列来完成矩阵.

For example, the simplest padding function is to complete the matrix with an initial row and column.

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

在这里，我们必须小心其余部分，因为我们正在定义它，因此请使用上面定义的zipWith'.换句话说，我们必须确保如果将undefined传递给rowCol row col，我们仍然可以看到可以从中生成矩阵其余部分的初始值.

Here we have to be careful to be lazy in the remainder, since we're in the middle of defining it, hence the use of zipWith' defined above. Said another way, we must ensure that if we pass undefined to rowCol row col we can still see the initial values that the rest of the matrix can be generated from.

现在pascals可以定义如下.

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

---

用于截断无限矩阵的助手:

---

Helper to truncate infinite matrices:

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

这篇关于双递归定义列表的双重无限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！