Haskell: 中缀运算符（`:`）是否有左侧身份？

Question

换句话说，在下面的filter实现中，我可以使用什么语法（如果有）来代替XXX？

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' f (x:xs) =
  let n = if f x then x else XXX
  in  n:(filter' f xs)

我知道以下的替代实现（它是递归且仅在前面添加），但如果中缀运算符具有LHS标识符，我仍然很好奇。

filter' :: (a -> Bool) -> [a] -> [a]
filter' _ []     = []
filter' f (x:xs)
  | f x = x:(filter' f xs)
  | otherwise = filter' f xs

- iceman

---

“:`”是一个构造函数。构造函数没有身份。 - alternative

Answer 1

没有的。这是因为可以看到

ghci> length (undefined : [])
1

无论您放置哪个元素，都将始终获得长度为1。

这种措辞如何？

filter' f (x:xs) =
    let n = if f x then (x:) else id
    in  n (filter' f xs)

- luqui

---

甚至更短的写法是：(if f x then (x:) else id) (filter' f xs)。 - user2407038

Answer 2

手势警报：以下严格来说是谎言（因为有undefined等），但它仍然是一个有用的想法。

Haskell中使用data声明定义的类型的一个关键属性是它们是free的：该类型的值集合同构于该类型的正常形式术语（完全求值表达式）的集合。如果该类型的两个术语不同，则它们具有不同的值。

由此可见，在相同作用域内，x : xs和xs必须是不同的列表，因为它们是不同的术语。

换句话说，data类型的语义是，如果您在构造函数应用程序上进行模式匹配，则始终会返回相同的构造函数及其参数。例如，无论x和xs是什么，这两个表达式都保证是True：

case [] of
    []   -> True
    x:xs -> False

case (x:xs) of
    []     -> False
    x':xs' -> x == x' && xs == xs'

你所寻找的左单位元将成为第二个表达式的反例。因此，这样的值不存在。

- Luis Casillas

Answer 3

虽然没有，但++确实有一个身份，即[]。因此，这也可以起作用：

filter' _ [] = []
filter' f (x:xs) =
     let n = if f x then [x] else [] 
     in n ++ (filter' f xs)

这与@luqui的答案相同（您可以证明），只是不太高效，但它保持了一些低阶特性。

- yatima2975

---

老实说，我怀疑它的效率并没有降低。找出答案会很有趣。 - luqui

更好的写法：filter' f (x:xs) = [x | f x] ++ filter' f xs - effectfully

@luqui：你的解决方案可以简化为 if f x then x : filter' f xs else filter' f xs，比我的稍微快一点（不需要内联定义 ++）- 但是，是的，我对效率的猜测假定了一个极其天真的执行模型，我想 GHC 在任何优化级别下都会为两者生成相同的代码 :-) - yatima2975