功能“成员"的实现可通过以下方式实现:使用“文件夹"在Haskell [英] Implementation of function "member" using "foldr" in Haskell

问题描述

我这样尝试过:

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'

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

I don't know what it means... can someone help me?

PS:member是一个函数，在给定一个元素和一个元素列表的情况下，该函数返回该元素是否属于该列表.常见的实现方式是:

PS: member is a function that, given a element and a list of elements, returns whether the element belongs to that list or not. The usual implementation is:

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 一个显式类型签名会更好，我猜您想要的是

You're almost there, but as you can see your types don't line up. It would have been better if you had given member an explicit type signature, I'm guessing that you want something like

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

这会使编译器抱怨这不是类型检查，而是在您尝试使用它时失败.问题是 folder(==)的类型为 Bool->[布尔]->布尔，不是您所期望的那样.

This would have made the compiler complain that this doesn't type check instead of failing when you tried to use it. The problem is that foldr (==) has the type Bool -> [Bool] -> Bool, not quite what you were expecting.

相反，您想要的是更多类似的东西

Instead, what you want is something more like

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

我在这里将参数分成几行，以便更轻松地查看 folder 的参数是什么.这里的一个好主意是将值列表转换为 Bool 的列表，然后使用or运算符( || )将列表简化为单个布尔.由于Haskell在默认情况下是惰性的，因此 map(e ==)xs 实际上不会计算任何内容，直到 folder 需要元素时，因此您不必比较每个元素列表中的 e .

I've split up the arguments onto separate lines here so that it's easier to see what the arguments to foldr actually are. The big idea here is to convert the list of values into a list of Bools, then use the or operator (||) to reduce the list into a single Bool. Since Haskell is lazy by default, map (e ==) xs won't actually compute anything until elements are needed by foldr, so you won't necessarily compare every element in the list to e.

您可以仅使用具有更复杂的累加器的 folder 直接实现此功能( foldr 的第一个参数):

You could implement this directly with only foldr with a more complicated accumulator (the first argument to 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 ==)的原因，我只是将执行比较的步骤与累积值的步骤分开了.

Notice how in this case we have to perform e == x for every x in xs until we find a case where acc is True. This is why I chose map (e ==) earlier, I just separated the step of performing the comparison from the step of accumulating the values.

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

One thing to keep in mind with foldr (and most other folds) is that the second argument, also called the initial value, has to have the same type as final result of foldr. In this case you're wanting foldr to return a Bool, so the second argument must be a Bool as well.

如果您拥有足够新版本的GHC，解决这些问题的技巧就是打孔.这些允许您在表达式中放入空洞"，编译器会告诉您该空洞应该是什么类型，

A trick for working through these problems, provided you have a new enough version of GHC, is typed holes. These allow you to put in "holes" in an expression and the compiler will tell you what type that hole should be, so if you do

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

这告诉您赋予 folder 的函数必须具有类型 a->.布尔->Bool 和初始值必须具有 Bool 类型.由于 e 的类型为 a ，因此您不能将其原样放置在该孔中.这种技术可以帮助您指导您定义函数，特别是当您不确定所有类型时，编译器会告诉您对每个参数使用什么.

This tells you that the function given to foldr must have the type a -> Bool -> Bool and the initial value must have type Bool. Since e has type a you can't put it as is in that hole. This technique can help guide you through defining your functions, particularly when you aren't sure of all the types, with the compiler telling you what to use for each argument.

这篇关于功能“成员"的实现可通过以下方式实现:使用“文件夹"在Haskell的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！