递归还是列表推导？

Question

我正在学习《Learn You a Haskell For Great Good》中的高阶函数章节，作者在其中实现了几个不同的库函数。当作者来到重新实现标准库函数filter的filter'函数定义时，我认为显而易见的是:

filter' f xs = [x | x <- xs, f x]

但作者提供了以下更长的递归定义：

filter' _ [] = []  
filter' p (x:xs)   
    | p x       = x : filter' p xs  
    | otherwise = filter' p xs

这两个定义做的事情是一样的。有什么原因吗？递归定义是否更高效？对于Haskell来说更符合惯用法吗？还是其他原因？

- JSBձոգչ

---

filter' 也可以用高阶函数 foldr 来表示，比如 filter' p = foldr (\x ys -> if p x then x : ys else ys) []，虽然这更像是高阶函数的使用示例而不是如何“从头开始”构建一个高阶函数。 - hammar

如果您对它们的解糖方式感兴趣，请参阅Haskell 2010>表达式>列表推导式。 - Dan Burton

Answer 1

这可能是因为列表推导只是语法糖，原则上被转换为递归形式。

如果作者的重点是说明函数如何实现，使用列表推导快捷方式并不能真正做到这一点 - 它展示了一种表达解决方案的替代方式，但并不是真正的功能实现。

简而言之，它展示了如何从相当少量的基本构建块实现。

不过这只是我的猜测 - 我自己没有阅读过那篇教程。

- user180247

Answer 2

列表推导式在某种程度上相当于一个 map 和 filter 操作的组合，虽然在后端可能使用 concatMap。通常情况下，使用更高级的抽象工具实现更低级别的操作是不可取的。

- alternative

---

@augustss 你为什么认为我特别提到它使用了concatMap？我的意思是filter基本上是concatMap的一部分。 - alternative

“可以使用”听起来不像“必须使用”。 :) - augustss

我认为Augustss在这里的观点是，concatMap 完全包含了 map 和 filter 的功能，同时还能做它们无法完成的事情，并且任何重新实现列表推导的方法都必然等同于 concatMap。 - C. A. McCann

列表推导式可以被视为在列表单子中运作，其中赋值对应于绑定，条件指示一个守卫。如上所述，绑定实现需要 concatMap，而仅使用 map 和 filter 是不够的。据我所知，你无法用 map 和 filter 实现 concatMap。 - Sujay Jayakar

@Sujay concatMap = concat . map... 是的，它是基于 map 实现的，然后 filter 可以通过 concat Map 实现。 - alternative