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

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

6 голосов
/ 19 января 2011

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


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 аргумента. Почему это происходит? Спасибо.

Ответы [ 4 ]

9 голосов
/ 19 января 2011

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

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

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

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

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

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

8 голосов
/ 19 января 2011

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

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

3 голосов
/ 19 января 2011

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

2 голосов
/ 19 января 2011

Ответ Скотта верный, результат 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: я автор оригинального комментария:)

...