Сколько аргументов принимает функция foldr Haskell?

Question

Я новичок в Haskell, и я читаю книгу "Real World Haskell". В главе 4 книги автор спрашивает как упражнение переписать функцию groupBy с помощью fold. Один из читателей книги (Октавиан Voicu) дал следующее решение:

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 

Мой вопрос прост: Я знаю, что foldr принимает 3 аргумента: функцию, начальное значение и список. Но во второй строке кода foldr принимает 4 аргумента. Почему это происходит? Спасибо.

Answer 1

Ответ Скотта правильный, результат foldr является функцией, поэтому вот почему foldr принимает 4 аргумента. В foldr функции действительно принимает 3 аргумента (функция, база, список):

*Main> :type foldr 
foldr :: (a -> b -> b) -> b -> [a] -> b 

Я просто приведу здесь пример, который является менее сложным:

inc :: Int -> (Int -> Int) 
inc v = \x -> x + v 

test = inc 2 40 -- output of test is 42 

В приведенном выше коде, inc занимает одно аргумент v и возвращает функцию, которая увеличивает свой аргумент на v.

Как мы увидим ниже, тип возвращаемого inc 2 является функцией, поэтому ее аргумент можно просто добавить в конце:

*Main> :type inc 
inc :: Int -> Int -> Int 
*Main> :type inc 2 
inc 2 :: Int -> Int 
*Main> :type inc 2 40               
inc 2 40 :: Int 

Скобки могут использоваться, чтобы подчеркнуть, что возвращаемое значение является функцией , но функционально он идентичен коду выше:

*Main> (inc 2) 40 
42 

PS: Я автор оригинального комментария :)

Answer 2

В этом случае foldr используется для создания функции. (\_ -> False) - аргумент этой функции.

Answer 3

Все функции в Haskell принимают только один аргумент. Когда у нас есть функция с типом a -> b -> c, это всего лишь более короткий способ написать a -> (b -> c), то есть функцию, которая принимает один аргумент и создает функцию, которая принимает другой аргумент. См. Currying для получения дополнительной информации.

В этом случае см. Ответ @ sepp2k. foldr создает функцию, и ей нужен другой («четвертый») аргумент.

Answer 4

В этой ситуации, я думаю, что лучше всего смотреть на тип подписи foldr:

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

и соответствовать выражению мы имеем (с добавленной скобкой для ясности):

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

Второй аргумент foldr - это тот же самый тип, что и его результат. В этом случае второй аргумент является функцией. В этом случае это означает, что выражение foldr с тремя аргументами будет функцией.

То, что вы видите как 4-й аргумент функции foldr, также можно рассматривать как первый аргумент результата foldr!