将递归防护更改为高阶函数 [英] Changing recursive guards into higher order functions

问题描述

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

I'm trying to convert basic functions into higher order functions (specifically map, filter, or foldr). I was wondering if there are any simple concepts to apply where I could see old functions I've written using guards and turn them into higher order.

我正在更改一个名为filterFirst的函数，该函数从列表中删除不满足给定谓词功能(第一个参数)的第一个元素(第二个参数).

I'm working on changing a function called filterFirst that removes the first element from the list (second argument) that does not satisfy a given predicate function (first argument).

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]

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

Based on the basic recursion, I was wondering if there might be a way to translate this (and similar functions) to higher order map, filter, or foldr. I'm not very advanced and these functions are new to me.

推荐答案

如果确实需要，我们可以使用foldr编写filterFirst，因为foldr有点通用"-它允许任何列表转换我们可以使用递归来执行.主要缺点是生成的代码是违反直觉的.我认为，在这种情况下，显式递归要好得多.

If we really want, we can write filterFirst using foldr, since foldr is kind of "universal" -- it allows any list transformation we can perform using recursion. The main downside is that the resulting code is rather counter-intuitive. In my opinion, explicit recursion is far better in this case.

无论如何，这是完成的过程.这依赖于我认为是反模式的东西，即将四个参数传递给foldr".我将其称为反模式，因为foldr通常仅使用三个参数来调用，而结果不是使用第四个参数的函数.

Anyway here's how it is done. This relies on what I consider to be an antipattern, namely "passing four arguments to foldr". I call this an antipattern since foldr is usually called with three arguments only, and the result is not a function taking a fourth argument.

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进行调用，则将返回过滤后的列表.如果我们使用

Clear? Not very much. The trick here is to exploit foldr to build a function Bool -> [a] which returns the original list if called with False, and the filtered-first list if called with True. If we craft that function using

foldr go baseCase xs

结果显然是

foldr go baseCase xs True

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

Now, the base case must handle the empty list, and in such case we must return a function returning the empty list, whatever the boolean argument is. Hence, we arrive at

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

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

Now, we need to define go. This takes as arguments:

1. 列表元素y
2. 递归" ys的结果(其余列表的功能Bool->[a])

1. a list element y
2. the result of the "recursion" ys (a function Bool->[a] for the rest of the list)

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

and must return a function Bool->[a] for the larger list. So let's also consider

1. 布尔参数

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

and finally make go return a list. Well, if the boolean is False we must return the list unchanged, so

go y ys False = y : ys False

请注意，ys False的意思是尾巴未变"，因此我们实际上是在重建整个列表而未变.

Note that ys False means "the tail unchanged", so we are really rebuilding the whole list unchanged.

如果布尔值是true，我们将像p y一样查询谓词.如果那是假的，我们丢弃y，并返回列表尾部不变

If instead the boolean is true, we query the predicate as in p y. If that is false, we discard y, and return the list tail unchanged

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

如果p y为true，则保持y并返回列表尾部经过过滤的内容.

If p y is true, we keep y and we return the list tail filtered.

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

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

As a final note, we cold have used a pair ([a], [a]) instead of a function Bool -> [a], but that approach does not generalize as well to more complex cases.

仅此而已.知道这项技术很高兴，但是我不建议在真正的代码中推荐它，以免被其他人理解.

So, that's all. This technique is something nice to know, but I do not recommend it in real code which is meant to be understood by others.

这篇关于将递归防护更改为高阶函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！