CODEWITHSUNDEEP
haskellfold
Cookiemonstrosity
Cookiemonstrosity

Reputation: 83

Type error with foldr groupBy implementation

I'm stuck on implementing groupBy with a foldr. For some reason when I change a guard condition, the type signature goes ape on me.

I can compile this, albeit its incorrect:

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

But this does not compile:

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

giving me this error.

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

I don't get it. Using "f x y" makes it not compile and spit out this error, but when I replace f x y with either True or False, it compiles. I wanna know how I can return []:(y:ys) when "f x y" is true.

Upvotes: 3

Views: 174

Answers (1)

Sassa NF
Sassa NF

Reputation: 5406

Well, in short, the first version y is of type [a], as it is not bound by type signature of f, and the second you bind y to be of type a.

Notice that (y:ys) of step is of type [[a]], so you really want something like

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

Upvotes: 5

Related Questions