haskell - 在 Haskell 中使用 "member"实现函数 "foldr"

Question

我这样试过:

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] ) )

Answer 1

您快完成了，但是您可以看到您的类型没有对齐。如果你给member会更好一个明确的类型签名，我猜你想要类似的东西

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

这会让编译器提示说这不会在您尝试使用它时进行类型检查而不是失败。问题是 foldr (==)类型为 Bool -> [Bool] -> Bool ，与您的预期不尽相同。

相反，你想要的是更像

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

我在这里将参数拆分到单独的行中，以便更容易看到 foldr 的参数是什么实际上是。这里的主要想法是将值列表转换为 Bool 的列表。 s，然后使用 or 运算符 ( || ) 将列表缩减为单个 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在 xs直到我们找到 acc 的情况是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你不能把它放在那个洞里。这种技术可以帮助指导您定义函数，特别是当您不确定所有类型时，编译器会告诉您每个参数使用什么。