list - Haskell - 使用 foldr 函数对列表元素进行分组

Question

这是 Haskell 中的作业。我们的任务是使用 foldr 函数定义各种函数。

我们得到了一个类型:

group :: Eq a => [a] -> [[a]]

并被要求这样定义它:

group [1,2,2,3,4,4,4,5] = [[1], [2,2], [3], [4,4,4], [5]]
group [1,2,2,3,4,4,4,5,1,1,1] = [[1], [2,2], [3], [4,4,4], [5], [1,1,1]]

这是我目前所拥有的:

group = foldr (\x xs -> if x == head (head xs) then (x : head xs) : xs else (x : []) : (head xs) : xs )

但是当我尝试将其加载到 ghci 解释器中时，我收到以下错误消息:

Couldn't match type `[a0] -> [a]' with `[[a]]'
Expected type: [a] -> [[a]]
  Actual type: [a] -> [a0] -> [a]
In the return type of a call of `foldr'
Probable cause: `foldr' is applied to too few arguments
In the expression:
  foldr
    (\ x xs
       -> if x == head (head xs) then
              (x : head xs) : xs
          else
              (x : []) : (head xs) : xs)
In an equation for `group':
    group
      = foldr
          (\ x xs
             -> if x == head (head xs) then
                    (x : head xs) : xs
                else
                    (x : []) : (head xs) : xs)

如果有人能解释我的代码无法按预期工作的任何原因，我们将不胜感激。谢谢。

Answer 1

我认为你走在正确的轨道上，所以我会尽量把你的想法写得更好一些。我想说的是:你应该把 foldr 的第一个参数拉出来放到一个函数中，再做一次模式匹配:

group :: Eq a => [a] -> [[a]]
group = foldr f undefined
  where f x []        = undefined
        f x (ys@(y:_):yss)
          | x == y    = undefined
          | otherwise = undefined

这应该可以 - 现在你只必须在我放置undefined的地方放置正确的东西:)

待会儿我会回来做完的

---

好吧，我猜你放弃了或者什么的——无论如何这是一个解决方案:

group :: Eq a => [a] -> [[a]]
group = foldr f []
  where f x []        = [[x]]
        f x (ys@(y:_):yss)
          | x == y     = (x:ys):yss
          | otherwise = [x]:ys:yss

还有一些例子:

λ> group []
[]
λ> group [1]
[[1]]
λ> group [1,1]
[[1,1]]
λ> group [1,2,1]
[[1],[2],[1]]
λ> group [1,2,2,3,4,4,4,5]
[[1],[2,2],[3],[4,4,4],[5]]

请注意 f 的模式并不详尽(这没问题 - 想想为什么) - 当然，如果你愿意，你可以扩展它(如果你不同意 group [] = [] 比你必须的。