可以改进我的过滤器实施吗？

Question

第一原则 Haskell 中的一个练习说要使用 foldr 实现 filter，这就是我想出的，但感觉和看起来都很笨拙。有没有更自然的方法来实现它 foldr?

import Data.Bool
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter f = foldr (\x -> bool (++ []) ((:) x) (f x)) []

Answer 1

您可以使用 (->) a 的 Applicative 实例来使 lambda 更干净。但是，如果你想使用 foldr，我认为你不会有任何实质性的改变：

myFilter f = foldr (bool id <$> (:) <*> f) []

bool id <$> (:) <*> f表示\x -> bool id ((:) x) (f x)。 bool id 的类型为 ([a] -> [a]) -> Bool -> ([a] -> [a])。 (:) 的类型为 a -> [a] -> [a]，f 的类型为 a -> Bool。当 (<$>) 和 (<*>) 以这种方式使用时，您可以认为它假装 (:) 和 f 没有 a 参数，使他们 [a] -> [a] 和 Bool，分别将它们应用到 bool id 得到 [a] -> [a]，然后通过重新引入 a 参数来结束谎言，使 [= =19=]。运算符负责 a 周围的线程，因此您不需要 lambda 抽象。

Answer 2

我会只使用bool如果它让我简单地摆脱lambda表达式，通过使用谓词bool组合调用p：bool iffalse iftrue . p。但是，p 并不是唯一需要在列表元素上调用的函数； (:) 也一样。您可以使用函数的Applicative实例来编写

myfilter p = foldr (bool id . (:) <*> p) []  -- yuck

但在这种情况下，我只会在 lambda 表达式中使用普通的 if 表达式：

myfilter p = foldr (\x -> if p x then (x:) else id) []  -- much clearer!

请注意，当专用于函数时，Applicative 的 (<*>) 运算符定义为 f <*> g = \x -> f x (g x)。我将其作为练习使用该定义将 bool id . (:) <*> p 转换为 \x -> bool id (x:) (p x).

Answer 3

与其仅仅搜索更优雅的实现，它可能会帮助您更多地学习搜索实现的优雅过程。这应该可以更轻松地找到优雅的解决方案。

对于列表中的任何函数 h，我们有

h = foldr f e

当且仅当

h [] = e
h (x:xs) = f x (h xs)

在这种情况下，您的 h 是 filter p 一些布尔函数 p 选择要保留的元素。将 filter p 作为 "simple" 递归函数实现并不难。

filter p [] = []
filter p (x:xs) = if p x then x : (filter p xs) else (filter p xs)

第一行表示e = []。第2行需要写成f x (filter p xs)的形式来匹配上面的h等式，以便我们推导出哪个f插入foldr。为此，我们只是抽象了这两个表达式。

filter p [] = []
filter p (x:xs) = (\x ys -> if p x then x : ys else ys) x (filter p xs)

所以我们发现，

e = [] 
f x ys = if p x then x: ys else ys

因此，

filter p = foldr (\y ys -> if p y then y : ys else ys) []

要详细了解这种使用 foldr 的方法，我建议阅读 "A tutorial on the universality and expressiveness of fold" 作者：格雷厄姆·赫顿。

一些补充说明：

如果这看起来过于复杂，请注意，虽然上述原则可以通过代数运算以这种 "semi rigorous" 方式使用，但它们可以而且应该用于指导您的直觉并帮助您进行非正式开发.

h (x:xs) = f x (h xs) 的等式阐明了如何找到 f。在 h 是过滤函数的情况下，您需要 f 将元素 x 与已过滤的尾部组合在一起。如果你真的理解这一点，应该很容易到达，

f x ys = if p x then x : ys else ys

Answer 4

是的，有：

myFilter :: (a -> Bool) -> [a] -> [a]
myFilter f = foldMap (\x -> [x | f x])

> myFilter even [1..10]
[2,4,6,8,10]

看，我用 foldMap 打开了你。

嗯，foldr 是 foldr (\x -> ([x | f x] ++)) []。

可以改进我的过滤器实施吗？

Can my implementation of filter be improved?

haskell

fold