我是否在使用关于滤波器定义的声音等式推理？

Question

这是使用foldr的过滤器函数的定义：

myFilter p xs = foldr step [] xs
    where step x ys | p x       = x : ys
                    | otherwise = ys

例如，假设我有这样的函数：

myFilter odd [1,2,3,4]

因此，将是：

foldr step [] [1,2,3,4]

而这将是

step 1 (foldr step [] [2,3,4])

而这将是

step 1 (step 2 (foldr step [] [3,4]))

而这将是

step 1 (step 2 (step 3 (foldr step [] [4])))

而这将是

step 1 (step 2 (step 3 (step 4 (foldr step [] []))))

foldr step [] []是[]，所以：

step 1 (step 2 (step 3 (step 4 [])))

现在，我们将实际进入step函数。

下面是step在myFilter函数中的定义，如下所示：

step x ys | p x       = x : ys
          | otherwise = ys

另外，我提醒您，在我们的示例中，p实际上是odd函数。

又一次，我们来到这里：

step 1 (step 2 (step 3 (step 4 [])))

和

x = 4在最内部的step中，4并不奇怪，所以我们返回ys，也就是[]

所以现在我们知道了：

step 1 (step 2 (step 3 []))

现在，在最内部的step中，x = 3和3是奇怪的，所以我们返回x:ys，它是3 : []，也就是[3]，现在我们得到：

step 1 (step 2 [3])

现在，在内部step中，x = 2和2并不奇怪，所以我们返回ys，即[3]，所以现在我们将得到：

step 1 [3]

现在，x = 1和1是奇怪的，所以我们返回x : ys，它是1 : [3]，也就是[1,3]。

结尾:-)。

我所有的动作都对吗？

非常感谢:-)

附注：myFilter的定义来自于第四章中的一书。

Answer 1

这个在我第一次读的时候看起来很对。

但是，重要的是，为了实现懒惰的评估，Haskell实际上会以另一种方式看待事物。换句话说，真正的序列更像是

step 1 (step 2 (step 3 (step 4 [])))

变成了

step 1 <block1>

变成

[1, <block1>]

然后，如果尝试从该列表中提取下一个元素，它将计算

[1, step 2 <block2>]

变成

[1, <block2>]

然后试着评估

[1, step 3 (step 4 [])]

转成

[1, step 3 <block3>]

变成

[1, 3, <block3>]

等等，我花了一段时间才明白。这与我的直觉相反，因为foldr似乎是从“内到外”来计算的，而foldl则是从“外部”来计算的，所以foldr会很懒(实际上是这样)，而foldl则是严格的。但是，如果你像我上面所描述的那样思考它，这是有意义的(无论如何，对我来说)。

Answer 2

只是为了扩展懒散的计算顺序:基本上，Haskell总是先计算函数，而不是在必须的情况下查看参数。

如果使用了对myFilter的调用结果(例如，打印)，则将按以下顺序计算该函数：

myFilter odd [1,2,3,4]

首先对myFilter函数进行评估：

foldr step [] [1,2,3,4]

现在，foldr是最外层的函数，并得到评估：

step 1 (foldr step [] [2,3,4])

现在，step会得到生成1的计算结果，因为1是奇怪的：

1 : foldr step [] [2,3,4]

现在，结果列表的第一个元素是可用的，可以由调用函数使用。如果调用函数也使用以下元素，则计算将继续使用foldr

1 : step 2 (foldr step [] [3,4])

step的评估现在不会产生任何新元素，因为2是偶数：

1 : foldr step [] [3,4]

因此，foldr再次表示：

1 : step 3 (foldr step [] [4])

现在评估step产生了3

1 : 3 : foldr step [] [4]

评价foldr；

1 : 3 : step 4 (foldr step [] [])

和step再一次：

1 : 3 : foldr step [] []

最后，foldr计算为空列表：

1 : 3 : []

Answer 3

乍一看，您在具体示例中所采取的步骤似乎是正确的。但是，我想指出的是，filter和foldr都可以有效地应用于无限列表--就Haskell而言，这应该表明您的步骤顺序是不正确的。