使用文件夹制作过滤器

Question

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

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，退货x，否则跳过它。foldr起作用的方式是，它不断在xs传递的列表上循环。那我为什么要做

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

并告诉它继续进行，xs即使foldr已经进行了？

Answer 1

foldr :: (a -> b -> b) -> b -> [a] -> b在as 的输入列表上循环并操纵a b（表示循环的状态）。op的工作是a从输入列表中获取当前状态b，然后计算一个新状态。foldr确保op为列表中的每个项目调用该方法。

在您的情况下filter，b碰巧也是的列表a。因此，您的代码正在讨论as的两个不同列表-输入列表和输出列表。您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

因此，当我们currentOutput从返回时addToOutputIfNecessary，并不是foldr要继续。（foldr将始终单独继续下一个输入元素-您无需告诉它继续。）只是说循环的状态并未更改此迭代；我们决定不向输出列表添加项目。

希望这可以帮助！如果您不了解任何内容，请在评论中让我知道。

Answer 2

foldr封装将列表中的元素组合在一起以及折叠列表的其余部分的结果所涉及的递归。xs不是您输入内容的尾巴；这是折叠输入尾部的结果。

您可以通过专注于您想做op的事情，并通过重构来不强调它的作用，从而对此加以强调

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

可以减少到

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

换句话说，给定列表的第一个元素，您将如何处理它：将x其添加到递归结果之前，还是按原样返回该结果？