在 Haskell 中使用“foldr”实现“member”函数

我这样尝试过：

member e [] = False
member e xs = foldr (==) e xs

进而：

member 3 [1,2,3,4,5]

我收到此错误消息：

No instance for (Num Bool) arising from the literal `3'
In the first argument of `memb', namely `3'

我不知道这意味着什么...有人可以帮助我吗？

PS：member 是一个函数，给定一个元素和一个元素列表，返回该元素是否属于该列表。通常的实现是：

member a [] = False
member a (x:xs) | (a == x)  = True
                | otherwise = member a xs

PS2：完整代码

-- member:: Int -> [Int] -> Bool (Not necessary)
member e [] = False
member e xs = foldr (==) e xs

main = do
    putStrLn (show( member 3 [1,2,3] ) )

你已经快到了，但正如你所看到的，你的类型没有对齐。如果你给予的话那就更好了member一个显式的类型签名，我猜你想要类似的东西

member :: (Eq a) => a -> [a] -> Bool

这会让编译器抱怨这不会进行类型检查，而不是在您尝试使用它时失败。问题是foldr (==)有类型Bool -> [Bool] -> Bool，不完全符合您的预期。

相反，你想要的更像是

member e xs
    = foldr (||)
            False
            (map (e ==) xs)

我在这里将参数分成不同的行，以便更容易查看参数的内容foldr实际上是。这里的主要想法是将值列表转换为列表Bools，然后使用或运算符 (||) 将列表缩减为单个Bool。由于 Haskell 默认是惰性的，map (e ==) xs在需要元素之前不会实际计算任何内容foldr，因此您不必将列表中的每个元素与e.

你可以直接实现这个foldr使用更复杂的累加器（第一个参数foldr):

member e xs = foldr (\x acc -> if acc then x else e == x) False xs

这可以等效地写为

member e xs = foldr (\x acc -> acc || e == x) False xs

注意在这种情况下我们必须如何执行e == x对于每一个x in xs直到我们找到一个案例acc is True。这就是我选择的原因map (e ==)早些时候，我只是将执行比较的步骤与累加值的步骤分开。

需要记住的一件事foldr（和大多数其他折叠）是第二个参数，也称为初始值，必须具有与最终结果相同的类型foldr。在这种情况下你想要foldr返回一个Bool，所以第二个参数必须是Bool以及。

如果您有足够新的 GHC 版本，解决这些问题的一个技巧就是键入漏洞。这些允许您在表达式中放入“洞”，编译器会告诉您该洞应该是什么类型，所以如果您这样做

member :: Eq a => a -> [a] -> Bool
member e xs = foldr _1 _2 xs

GHC 将打印出来

Found hole `_1` with type: a -> Bool -> Bool
...
Relevant bindings include
  xs :: [a]
  e :: a

Found hole `_2` with type: Bool
...
Relevant bindings include
  xs :: [a]
  e :: a

这告诉您赋予的函数foldr必须有类型a -> Bool -> Bool并且初始值必须具有类型Bool。自从e有类型a你不能把它按原样放进那个洞里。这种技术可以帮助指导您定义函数，特别是当您不确定所有类型时，编译器会告诉您每个参数使用什么。