Haskell 函数 returns 列表中出现次数超过给定数量的元素列表

Question

我尝试制作一个函数，如标题所示，它有两个参数，一个指定该数字必须出现多少次的数字和一个我们正在处理的列表，我制作了一个函数来计算给定的出现次数列表中的数字，我尝试在我的主要功能中使用它，但我无法理解 if else 和缩进在 Haskell 中是如何工作的，修复错误比在其他语言，我想我遗漏了 else 语句，但即便如此我也不知道该把它放在那里

count el list = count el list 0
     where count el list output
             | list==[] = output
             | head(list)==el = count el (tail(list)) output+1
             | otherwise = count el (tail(list)) output


moreThan :: Eq a => Int -> [a] -> [a]
moreThan a [] = []
moreThan a list = moreThan a list output i
    where moreThan a list [] 0
            if i == length (list)
                then output
            else if elem (list!!i) output
                 then moreThan a list output i+1
            else if (count (list!!i) list) >= a 
                then moreThan a list (output ++ [list!!i]) i+1

我现在得到的只是

parse error (possibly incorrect indentation or mismatched brackets)

Answer 1

您只是忘记了 = 符号和一些括号，以及最后的 else 大小写。但是你也改变了内部函数声明和调用的顺序：

    moreThan :: Eq a => Int -> [a] -> [a]
    moreThan a [] = []
    moreThan a list = go a list [] 0   -- call
        where go a list output i =      --  declaration  =
                if i == length (list)
                    then output
                else if elem (list!!i) output
                     then go a list output (i+1)    -- (i+1) !
                else if (count (list!!i) list) >= a 
                    then go a list (output ++ [list!!i]) (i+1)   -- (i+1) !
                else
                    undefined

我确实将您的内部函数重命名为 go，这是惯例。

至于一般如何修复错误，请慢慢仔细地阅读错误消息——他们通常会说明哪里出了问题。

这解决了您提出的语法问题。

至于在缺少的 else 子句中放入什么，您刚刚在它上面的行中处理了这个问题——如果第 ith 个元素在列表中，您将其包含在输出中大于或等于给定参数 a。做什么else，我们在else子句中说。

也就是说，最有可能的是，不在输出中包含该元素：

                    then go a list (output ++ [list!!i]) (i+1)
                else               ---------------------
                    undefined

因此，只保留 output 原样，而不是轮廓部分，并用该行代替 undefined。

更重要的是，通过索引访问列表元素是一种反模式，最好通过在每个递归步骤中采用 tail 来“滑动”，并始终处理 head 元素，就像您在 count 代码中所做的那样（但最好使用模式匹配，而不是直接使用那些函数）。这样我们的代码就变成了线性的而不是像现在这样的二次方的。

Answer 2

Will Ness 的回答是正确的。我只是想为 Haskell 提供一些一般性建议以及一些改进代码的技巧。

首先，我总是避免使用守卫。该语法与 Haskell 的通常票价非常不一致，并且守卫不能像其他 Haskell 语法那样组合。如果我是你，我会坚持使用 let、if/then/else 和模式匹配。

其次，Haskell 中的 if 陈述通常不是正确答案。在许多情况下，最好避免完全（或至少尽可能多地）使用 if 语句。例如，count 的可读性更高的版本如下所示：

count el list = go list 0 where
    go [] output = output
    go (x:xs) output = go xs (if x == el
                              then 1 + output
                              else output)

但是，这段代码仍然存在缺陷，因为它在 output 中不够严格。例如，考虑表达式 count 1 [1, 1, 1, 1] 的计算，其过程如下：

count 1 [1, 1, 1, 1]
go [1, 1, 1, 1] 0
go [1, 1, 1] (1 + 0)
go [1, 1] (1 + (1 + 0))
go [1] (1 + (1 + (1 + 0)))
go [] (1 + (1 + (1 + (1 + 0))))
(1 + (1 + (1 + (1 + 0))))
(1 + (1 + 2))
(1 + 3)
4

请注意此评估的膨胀 space 用法。我们需要强制 go 以确保 output 在进行递归调用之前被求值。我们可以使用 seq 来做到这一点。表达式 seq a b 的计算如下：首先，a 被部分计算。然后，seq a b 的计算结果为 b。对于数字，“部分评估”与完全评估相同。

所以代码实际上应该是

count el list = go list 0 where
    go [] output = output
    go (x:xs) output = 
        let new_output = if x == el
                         then 1 + output
                         else output
        in seq new_output (go xs new_output)

使用这个定义，我们可以再次跟踪执行：

go [1, 1, 1, 1] 0
go [1, 1, 1] 1
go [1, 1] 2
go [1] 3
go [] 4
4

这是计算表达式的更有效方法。在不使用库函数的情况下，这基本上和编写 count 函数一样好。

但我们实际上使用的是一种非常常见的模式 - 一种如此常见的模式，有一个以它命名的高阶函数。我们正在使用 foldl'（必须使用语句 import Data.List (foldl') 从 Data.List 导入）。此函数具有以下定义：

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f = go where
    go output [] = output
    go output (x:xs) =
       let new_output = f output x
       in seq new_output (go new_output xs)

所以我们可以进一步重写我们的count函数为

count el list = foldl' f 0 list where
    f output x = if x == el
                 then 1 + output
                 else output

这很好，但实际上我们可以通过将 count 步骤分成两部分来进一步改进此代码。

count el list 应该是 el 在 list 中出现的次数。我们可以将此计算分解为两个概念性步骤。首先，构造列表 list'，它由 list 中等于 el 的所有元素组成。然后，计算 list'.

的长度

在代码中：

count el list = length (filter (el ==) list)

在我看来，这是迄今为止最易读的版本。由于懒惰，它也与 count 的 foldl' 版本一样高效。在这里，Haskell 的 length 函数负责找到执行 count 的计数部分的最佳方法，而 filter (el ==) 负责循环的部分，其中我们检查是否增加 output。通常，如果您正在遍历列表并有一个 if P x 语句，您通常可以将其替换为对 filter P.

的调用

我们可以用“无点风格”再写一次

count el = length . filter (el ==)

这很可能是函数在库中的编写方式。 .指函数组合。其含义如下：

要将函数 count el 应用于列表，我们首先过滤列表以仅保留 el == 的元素，然后取长度。

顺带一提，filter函数正是我们需要写的moreThan简洁的：

moreThan a list = filter occursOften list where
    occursOften x = count x list >= a

故事的寓意：尽可能使用高阶函数。

每当您解决 Haskell 中的列表问题时，您应该使用的第一个工具是 Data.List 中定义的函数，尤其是 map、foldl'/foldr、filter，和 concatMap。大多数列表问题归结为 map/fold/filter。这些应该是您首选的循环替代品。如果要替换嵌套循环，则应使用 concatMap.

Answer 3

以实用的方式，;)

moreThan n xs = nub $ concat [ x | x <- ( group(sort(xs))), length x > n ]

...或者以一种奇特的方式，哈哈

moreThan n xs = map head [ x | x <- ( group(sort(xs))), length x > n ]

...

mt1 n xs =  [ head x | x <- ( group(sort(xs))), length x > n ]

Haskell 函数 returns 列表中出现次数超过给定数量的元素列表

Haskell function that returns a list of elements in a list with more than given amount of occurrences

haskell

if-statement

indentation

parse-error