使用 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 是一个函数，给定一个元素和一个元素列表，returns 该元素是否属于该列表。通常的实现是：

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 列表，然后使用或运算符 (||) 将列表缩减为单个 Bool。由于 Haskell 默认情况下是惰性的，因此 map (e ==) xs 在 foldr 需要元素之前不会实际计算任何内容，因此您不必将列表中的每个元素与 [=25= 进行比较].

你可以只用 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

请注意，在这种情况下，我们必须对 xs 中的每个 x 执行 e == x，直到我们找到 acc 是 True 的情况。这就是我之前选择map (e ==)的原因，我只是将执行比较的步骤与累加值的步骤分开了。

foldr（和大多数其他折叠）要记住的一件事是第二个参数，也称为初始值，必须与 foldr 的最终结果具有相同的类型.在这种情况下，您希望 foldr 到 return 和 Bool，因此第二个参数也必须是 Bool。

如果您有足够新的 GHC 版本，解决这些问题的一个技巧是打孔。这些允许你在表达式中输入 "holes"，编译器会告诉你那个洞应该是什么类型，所以如果你这样做

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

GHC 将打印出来[=44=]

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 你不能把它按原样放在那个洞里。这种技术可以帮助指导您定义函数，特别是当您不确定所有类型时，编译器会告诉您每个参数使用什么。

Answer 2

我们知道，使用伪代码语法，

foldr g z []            = z
foldr g z [a,b,c,...,n] = g a (foldr g z [b,c,...,n])

我们知道我们希望它成为

member x []            = False
member x [a,b,c,...,n] = (x==a) || member x   [b,c,...,n]
                       = foldr g z [a,b,c,...,n] 
                       = g   a     (foldr g z [b,c,...,n])
                                   ------------------------ r
                       = (x==a) || (foldr g z [b,c,...,n])
                       = foldr g z [a,b,c,...,n] 
                           where 
                               { z     = False ; 
                                 g a r = (x==a) || r }  --- r

所以我们定义

的常规Haskell语法

member x  =  foldr g False  where  { g a r = (x==a) || r }

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

Implementation of function "member" using "foldr" in Haskell

haskell

member

fold