returns 最大列表和出现次数的函数

Question

我正在写一个递归函数mxAndC。当我给它一个列表时，它应该 return 一个元组。元组将给定列表的最大值作为其第一个元素，第二个元素将是该元素在列表中出现的次数。分配不允许我创建辅助函数。我期待以下输出：

mxAdC "bananas" = (s,1)

mxAdC "banana" =(n,2)

mxAdC [mod x 4 | x <- [1..50]] -> (3,12)

我做了以下事情：

mxAdC = go 0
 where go count (x:xs)  
           | count /= 0      = (mx, count)
           | null ((x:xs))   = error "The list is empty"
           | x == mx         = go (count+1) xs
         where mx = maximum (x:xs)

我遇到错误：

* Ambiguous type variable `a0' arising from a use of `go'
      prevents the constraint `(Ord a0)' from being solved.
      Relevant bindings include
        mxAdC :: [a0] -> (a0, Integer) (bound at hw06.hs:24:1)
      Probable fix: use a type annotation to specify what `a0' should be.
      These potential instances exist:
        instance (Ord a, Ord b) => Ord (Either a b)
          -- Defined in `Data.Either'
        instance Ord Ordering -- Defined in `GHC.Classes'
        instance Ord Integer
          -- Defined in `integer-gmp-1.0.0.1:GHC.Integer.Type'
        ...plus 23 others
        ...plus 38 instances involving out-of-scope types
        (use -fprint-potential-instances to see them all)
    * In the expression: go 0
      In an equation for `mxAdC':
          mxAdC
            = go 0
            where
                go count (x : xs)
                  | count /= 0 = (mx, count)
                  | null ((x : xs)) = error "The list is empty"
                  | x == mx = go (count + 1) xs
                  where
                      mx = maximum (x : xs)

我是 Haskell 的新手。有哪位仁慈的专家愿意伸出援手帮助这个新手吗？

Answer 1

你遇到了可怕的单态限制。

您可以通过

修复类型错误

使用mxAdC x = go 0 x
将 {-# LANGUAGE NoMonomorphismRestriction #-} 放在文件的开头
添加类型签名

你的函数仍然是错误的，但现在它进行了类型检查。

Haskell 禁止看起来像顶级常量的多态函数（在 = 符号之前不要有参数）。所以一般来说你不能减少eta（用foo = bar替换foo x = bar x）。完整的解释相当长 - 请参阅此答案：

Answer 2

一个相当简单的实现将使用 filter:

mxAdC :: Ord a => [a] -> (a,Int)
mxAdC xs = (mx,length $ filter (\x -> x == mx) xs) where mx = maximum xs

Answer 3

其他人已经解释了类型错误。让我们看看更有趣的错误。

  | null ((x:xs))   = error "The list is empty"

怎么了？ x : xs 永远不会为空。不可能，因为它的第一个元素是x！你在这里的意思是

mxAdC ys
  | null ys = error "mxAdC: the list is empty"
  | otherwise = go 0 ys
  where ...

下一个问题是

  | count /= 0      = (mx, count)

这表示一旦计数不为零，您就完成了。所以你永远不会超过 1。你认识到你的递归需要一个基本情况，所以你试图放入一个，但你没有达到目标。您需要的基本情况是处理空列表：

go count [] = ?
go count (x:xs)  
  | x == mx         = go (count+1) xs

但是 go 中仍然缺少一些东西。 x /= mx 时你希望发生什么？您还需要添加一个案例（我留了问号让您填写）：

go count [] = ?
go count (x:xs)  
  | x == mx         = go (count+1) xs
  | otherwise       = ?

最后一个主要问题是您在 go 函数中定义了 mx。这将计算每次递交的列表 go 中任何部分的最大值。您要做的是在 mxAdC

中定义 mx

mxAdc ys
  | ....
  where
    go ...
    mx = maximum ys

还有两大效率问题需要处理。一个问题是 go 不再强制在递归调用中计算累加器，这可能会导致 space 泄漏。使用带有

的 BangPatterns 语言扩展可以轻松解决此问题

go !count [] = ?
go !count (x:xs)  
  | x == mx         = go (count+1) xs
  | otherwise       = ?

最后一个问题是你仍然遍历列表两次：一次计算最大值，然后再次计算它出现的次数。只需一次即可完成。我不会给你所有的细节，但基本的技巧是改变你的 go 函数来获取迄今为止看到的最大元素以及它被看到的次数。您必须调整 mxAdC 的其余部分以适应，使用模式匹配而不是 null.

returns 最大列表和出现次数的函数

A function that returns maximum of list and count of occurrences

recursion

haskell

functional-programming

higher-order-functions