haskell - foldr groupBy 实现的类型错误

Question

我坚持使用 foldr 实现 groupBy。出于某种原因，当我更改保护条件时，类型签名对我来说很奇怪。

我可以编译它，尽管它不正确:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]

groupBy' f xs = foldr step [] xs
    where    step x [] = [x] : []
             step x (y:ys)
                 | True = []:(y:ys)
                 | otherwise = (x:y):ys

但这不编译:

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]

groupBy' f xs = foldr step [] xs
    where    step x [] = [x] : []
             step x (y:ys)
                 | f x y = []:(y:ys)
                 | otherwise = (x:y):ys

给我这个错误。

Couldn't match type `a' with `[a]'
  `a' is an unknown type variable
Expected type: [[a]]
  Actual type: [a]
In the second argument of `(:)', namely `ys'
In the expression: (x : y) : ys
In an equation for `step':
    step x (y : ys)
      | f x y = [] : (y : ys)
      | otherwise = (x : y) : ys

我不明白。使用“f x y”使其无法编译并吐出此错误，但是当我将 f x y 替换为 True 或 False 时，它​​会编译。我想知道如何在“f x y”为真时返回 []:(y:ys)。

Answer 1

好吧，简而言之，第一个版本 y 是类型 [a]，因为它不受 f 类型签名的约束，然后将 y 绑定(bind)为 a 类型。

请注意 step 的 (y:ys) 是 [[a]] 类型，所以您真的想要类似的东西

step x ((y:ys):yss) | f x y = (x:y:ys):yss
step x ys = [x]:ys