时间戳

首页 > 解决方案 > 计算列表中的出现次数

list - 计算列表中的出现次数

问题描述

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

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

标签： listhaskellcount

解决方案

这里有两个问题：一个与正确语法有关的错误，以及一个语义错误。

使用“多个”参数调用函数

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

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是的事实，(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来获取列表的头部（an a），以及列表上的递归结果（a b），从而构造一个新的类型结果b，然后是整个列表的结果。此外，该foldr函数接受一个值（类型b），该值是对应于空列表的值，然后它可以对列表（[a]）执行此操作，并返回该列表的值（a b）。

因此我们count看一下头元素，如果它等于我们搜索的元素，我们增加“累加器”，否则我们简单地传递它，我们可以将计数写为：

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

推荐阅读