使用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

我不明白.使用"fx y"使得它不会编译并吐出这个错误,但是当我用fn替换为True或False时,它会编译.当"fx y"为真时,我想知道如何返回[] :( y:ys).

Answer 1

嗯,总之,第一个版本y是类型的[a],因为它不会被类型特征的约束f,并绑定第二个y为类型a.

注意(y:ys)的step是类型的[[a]],所以你真的希望是这样

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