How many arguments takes the foldr function of Haskell?

Question

I am new to Haskell and I am reading the book "Real World Haskell". In the Chapter 4 of the book the author asks as an exercise to rewrite the groupBy function using fold. One of the readers of the book (Octavian Voicu ) gave the following solution:

theCoolGroupBy :: (a -> a -> Bool) -> [a] -> [[a]]
theCoolGroupBy eq xs = tail $ foldr step (\_ -> [[]]) xs $ (\_ -> False)
                       where step x acc = \p -> if p x then rest p else []:rest (eq x)
                                          where rest q = let y:ys = acc q in (x:y):ys

My question is simple: I know that foldr takes 3 arguments: a function, an initial value and a list. But in the second line of the code foldr takes 4 arguments. Why this happens? Thank you.

Answer 1

In this situation, I think it is best to look at the type signature of foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

and to match that to the expression we have (with added parenthesis for clarity):

(foldr step (\_ -> [[]]) xs) (\_ -> False)

The second argument of foldr is the same type as its result. In this case the second argument is a function. In this case, this means that the foldr expression with 3 arguments will be a function.

What you see to be the 4th argument of the foldr function could also be thought of as the 1st argument of the foldr result!

Answer 2

All functions in Haskell take just one argument. When we have a function with type a -> b -> c, it is just a shorter way to write a -> (b -> c), i.e. a function, which takes one argument and produces a function which takes another argument. See Currying for more information.

In this case, see the @sepp2k's answer. foldr produces a function and it needs another ("the 4th") argument.