计算列表中的出现次数

Question

我想计算Haskell中列表中元素的出现次数,但是有一个错误,我不知道为什么.

count:: Int -> [Int] -> Int
count n []= 0
count n (h:t) | (n `elem` (h:t)) =1+ count (n t) 
       | otherwise = count(n t)

Answer 1

这里有两个问题:错误与正确的语法有关,还有语义错误.

使用" 多个 "参数调用函数

编译器可能抱怨的错误与粗体部分有关:

count:: Int -> [Int] -> Int
count n []= 0
count n (h:t) | (n `elem` (h:t)) = 1+ count (n t)
              | otherwise = count (n t)

东西是对于其他语言编程第一大多数程序员相当混乱的是,一个人不能用括号内为功能应用.实际上,在许多编程语言中,如果有人写foo(1),那么在Haskell中你可以编写foo 1.

因此,Haskell解释了这样一个事实:你写count (n t)的count是is 的参数(n t),因此我们首先使用n函数和t参数执行函数应用程序.所以在Python中,这看起来像`count(n(t))``,这不是你的意思.

那么我们如何将多个参数传递给函数？好吧,在Haskell中,每个函数都只有一个参数.如果你写count n你基本上构建一个新的功能.通过将第二个参数应用于该新函数,我们因此" 链接 "了函数应用程序count n t,因此我们可以使用以下方法解决语法错误:

count:: Int -> [Int] -> Int
count n [] = 0
count n (h:t) | (n `elem` (h:t)) = 1+ count n t
              | otherwise = count n t

语义错误:elem而不是==？

但是现在还有一个语义错误:会n `elem` (h:t)怎么做？实际上它会检查是否n出现在列表中.因此,我们的函数在某些情况下会多次计算一个值.例如count 3 [1, 2, 3, 4]会导致3.自从3发生以来[1, 2, 3, 4],[2, 3, 4]和[3, 4].计数的想法是我们只查看头部,让递归查看剩余的元素,因此条件应该替换为:

count:: Int -> [Int] -> Int
count n [] = 0
count n (h:t) | n == h = 1 + count n t
              | otherwise = count n t

概括类型

现在我们可以使函数更通用:让函数在具有不同类型对象的列表上工作.事实上,只有一件事限制了这些类型:我们需要能够执行(==) :: Eq a => a -> a -> Bool它,因此我们可以将类型签名概括为:

count:: Eq a => a -> [a] -> Int
count n [] = 0
count n (h:t) | n == h = 1 + count n t
              | otherwise = count n t

算作特殊foldr功能

我们不是自己编写这个递归,而是可以使用foldr这个,这是列表中的一个变形.在foldr :: (a -> b -> b) -> b -> [a] -> b使用函数f :: a -> b -> b采用一个列表(一个的头a),和递归的列表(该结果b),因此,构造类型的一个新的结果b,即当为整个列表的结果.此外,该foldr函数接受一个值(类型b),该值是与空列表对应的值,然后它可以对list([a])执行此操作,并返回该列表的值(a b).

count因此我们看一下head元素,如果它等于我们搜索的元素,我们递增"累加器",否则我们简单地传递它,因此我们可以将count计为:

count:: Eq a => a -> [a] -> Int
count n = foldr (\x -> if n == x then (+1) else id) 0