6

好吧，这是使用 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]。

结束 ：-）。

我的所有动作都正确吗？
多谢 ：-）。

ps 的定义myFilter来自《Real World Haskell 》一书第 4 章。

4

3 回答 3

6

初读时这对我来说是正确的。

不过要记住的重要一点是，为了实现惰性求值，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严格的。但是，如果您按照我上面概述的方式来考虑它，那是有道理的（无论如何对我来说）。

于 2010-02-02T16:32:43.177 回答
4

只是为了扩展惰性评估顺序：基本上，Haskell 总是首先评估函数，直到它必须查看参数时才查看参数。

如果使用调用的结果myFilter（例如打印），则将按以下顺序评估该函数：

myFilter odd [1,2,3,4]

首先myFilter评估函数：

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

现在foldr是最外层的函数并被评估：

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

现在step被评估产生 a 1，因为1很奇怪：

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

现在结果列表的第一个元素可用并且可以由调用函数使用。如果调用函数还使用以下元素，则评估将继续foldr：

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

now的评估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 : []
于 2010-02-02T19:34:51.503 回答
2

乍一看，您在特定示例中采取的步骤看起来都是正确的。但是，我想指出，两者filter都foldr可以有效地应用于无限列表——这应该表明就 Haskell 而言，您的步骤顺序是不正确的。

于 2010-02-02T16:33:56.700 回答