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

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.这里的主要思想是将值列表转换为Bools 列表,然后使用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返回a Bool,所以第二个参数也必须是a 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你不能把它放在那个洞里.这种技术可以帮助指导您定义函数,特别是当您不确定所有类型时,编译器会告诉您每个参数使用的内容.