将递归防护更改为高阶函数

Question

我正在尝试将基本函数转换为高阶函数（特别是map，filter或foldr）。我想知道是否有任何简单的概念可以应用到我使用防护编写的旧函数并将其转换为更高阶的地方。

我正在更改一个称为filterFirst从列表中删除第一个元素（第二个参数）的函数，该列表不满足给定谓词函数（第一个参数）。

filterFirst :: (a -> Bool) -> [a] -> [a]
filterFirst _ [] = []
filterFirst x (y:ys)
    | x y       = y : filterFirst x ys
    | otherwise = ys

例如：

 greaterOne :: Num a=>Ord a=>a->Bool
 greaterOne x = x > 1

 filterFirst greaterOne [5,-6,-7,9,10]
 [5,-7,9,10]

基于基本的递归，我想知道是否可能有一种方法将此（以及类似的函数）转换为高阶映射，过滤器或文件夹。我不是很高级，这些功能对我来说是新的。

Answer 1

如果我们真的想要，我们可以编写filterFirstusing foldr，因为foldr它是一种“通用”——它允许我们使用递归执行任何列表转换。主要缺点是生成的代码相当违反直觉。在我看来，在这种情况下，显式递归要好得多。

无论如何，这是如何完成的。这依赖于我认为的反模式，即“向”传递四个参数foldr。我将其称为反模式，因为foldr通常仅使用三个参数进行调用，并且结果不是采用第四个参数的函数。

filterFirst :: (a->Bool)->[a]->[a]
filterFirst p xs = foldr go (\_ -> []) xs True
   where
   go y ys True 
      | p y = y : ys True 
      | otherwise = ys False
   go y ys False = y : ys False

清除？不是很多。这里的技巧是利用foldr构建一个函数Bool -> [a]，如果使用 调用False，则返回原始列表，如果使用 调用，则返回过滤优先列表True。如果我们使用

foldr go baseCase xs

结果显然是

foldr go baseCase xs True

现在，基本情况必须处理空列表，在这种情况下，我们必须返回一个返回空列表的函数，无论布尔参数是什么。因此，我们到达

foldr go (\_ -> []) xs True

现在，我们需要定义go. 这需要作为参数：

1. 一个列表元素y
2. “递归”的结果（列表其余部分的ys函数）Bool->[a]

Bool->[a]并且必须返回一个用于更大列表的函数。所以我们也考虑一下

3. 布尔参数

最后go返回一个列表。好吧，如果布尔值是，False我们必须返回列表不变，所以

go y ys False = y : ys False

请注意，这ys False意味着“尾部不变”，因此我们实际上是在不变地重建整个列表。

相反，如果布尔值为 true，我们将查询谓词，如 中所示p y。如果为假，我们丢弃y，并返回列表尾部不变

   go y ys True 
      | p y = -- TODO
      | otherwise = ys False

如果p y为真，我们保留y并返回过滤后的列表尾部。

   go y ys True 
      | p y = y : ys True
      | otherwise = ys False

最后一点，我们使用了pair([a], [a])而不是function Bool -> [a]，但是这种方法并不能推广到更复杂的情况。

所以，仅此而已。这种技术很值得了解，但我不推荐在实际代码中使用它，因为它是为了让其他人理解。