使用 foldr 制作过滤器

Question

我正在尝试使用 foldr 制作 filter。我有一个解决方案，但不知道为什么我的版本不起作用。

foldr 是这样工作的：

>>>foldr op z (xs:x)
x op z

然后重复，对吗？当 x 是列表中的最后一个元素时。

现在，我有

myFilter pred = foldr op z
  where
    z = []
    op x xs = if pred x then x

这不起作用，会出现 parse error (possibly incorrect indentation or mismatched brackets) 错误。

运算只给出x到pred，如果是true，returnsx，否则跳过。 foldr 的工作方式是它在传递的 xs 列表上不断循环。那么为什么我需要做

 op x xs = if pred x then x : xs else xs

并告诉它继续 xs 即使 foldr 已经在继续？

Answer 1

foldr :: (a -> b -> b) -> b -> [a] -> b 遍历 a 的输入列表并操作 b（表示循环的状态）。 op 的工作是从输入列表中取出一个 a，当前状态 b，并计算一个新状态。 foldr 确保为列表中的每个项目调用 op。

对于您的 filter，b 恰好也是 a 的列表。因此，您的代码正在讨论两个不同的 a 列表——输入列表和输出列表。您的 op 必须决定 我是否应该将此 x 放入输出列表？

澄清一下，这是您的代码，其中变量的命名更具暗示性。

filter :: (a -> Bool) -> [a] -> [a]
filter pred = foldr addToOutputIfNecessary initialOutput
  where
    initialOutput = []
    addToOuputIfNecessary itemFromInput currentOutput =
      if pred itemFromInput
      then itemFromInput:currentOutput
      else currentOutput

所以当我们从 addToOutputIfNecessary return currentOutput 时，并不是告诉 foldr 继续。（foldr 将始终自行继续下一个输入元素——您无需告诉它继续。）这只是说循环的状态没有改变本次迭代；我们决定不向输出列表添加项目。

希望这对您有所帮助！有什么不懂的可以在评论里告诉我。

Answer 2

让我们看一下 foldr 列表的类型：

foldr :: (a -> b -> b) -> b -> [a] -> b

现在你是这样使用它的：

foldr op z

从 foldr 的类型签名我们看到函数 op 必须 return 某种类型 b 与 z 相同的类型.既然你做 z = []，这一定是一个列表。所以op x xs的结果一定是一个列表。

此外，请记住 Haskell 中的 if...else 是一个 表达式 。这意味着无论条件是真还是假，它都必须评估某个值。在其他语言中，else 是可选的，因为 if 是一个语句。在Haskell中，else不是可选的。

So why do I need to do
op x xs = if pred x then x : xs else xs
and tell it to continue with xs even if foldr already does the continuing?

一个原因是 op 必须始终 return 一个值。 foldr 将使用此值继续其计算。没有它，foldr 将无法继续，事实上您的代码甚至不会像您看到的那样编译。

Answer 3

foldr 封装了将列表中的元素与折叠列表其余部分的结果组合所涉及的递归。 xs 不是你输入的尾部；这是折叠输入尾部的结果。

您可以通过重构 op 到做和 de-emphasizing 它的操作来强调这一点

op x xs = if pred x then x : xs else xs

到

-- (x:) xs == x:xs
-- id xs == xs
op x xs = (if pred x then (x:) else id) xs

可以是eta-reduced到

op x = if pred x then (x:) else id

换句话说，给定列表的第一个元素，您将如何处理它：将 x 添加到递归结果之前，或者 return 结果 as-is？

使用 foldr 制作过滤器

Making filter using foldr

haskell

fold