¿Cuántos argumentos toma la función foldr de Haskell?

Question

Soy nuevo en Haskell y estoy leyendo el libro "Real World Haskell". En el Capítulo 4 del libro, el autor pregunta como un ejercicio para reescribir la función groupBy usando fold. Uno de los lectores del libro (Octavian Voicu) dio la siguiente solución:

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 

Mi pregunta es simple: Sé que foldr toma 3 argumentos: una función, un valor inicial y una lista. Pero en la segunda línea del código, foldr toma 4 argumentos. ¿Por qué sucede esto? Gracias.

Answer 1

La respuesta de Scott es correcta, el resultado de foldr es una función, por eso parece que foldr toma 4 argumentos. Las funciones foldr tarda la 3 argumentos (función, base, lista):

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

Voy a dar aquí un ejemplo que es menos complejo:

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

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

En el código anterior, inc toma uno argumento, v, y devuelve una función que incrementa su argumento por v.

Como podemos ver a continuación, el tipo de retorno de inc 2 es una función, por lo que su argumento, simplemente se puede añadir al final:

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

Los paréntesis se podrían utilizar para enfatizar que el valor de retorno es una función , pero funcionalmente es idéntico al código anterior:

*Main> (inc 2) 40 
42 

PS: soy el autor del comentario original, :)

Answer 2

En este caso, foldr se utiliza para crear una función. (\_ -> False) es el argumento para esa función.

Answer 3

Todas las funciones en Haskell toman solo un argumento. Cuando tenemos una función con tipo a -> b -> c, es solo una manera más corta de escribir a -> (b -> c), es decir, una función que toma un argumento y produce una función que toma otro argumento. Vea Currying para más información.

En este caso, vea la respuesta de @sepp2k. foldr produce una función y necesita otro argumento ("el 4to").

Answer 4

En esta situación, creo que lo mejor es mirar a la firma tipo de foldr:

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

y para que coincida con la expresión que tenemos (con el paréntesis añadido para mayor claridad):

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

El segundo argumento de foldr es del mismo tipo que su resultado. En este caso, el segundo argumento es una función. En este caso, esto significa que la expresión foldr con 3 argumentos será una función.

¡Lo que parece ser el 4º argumento de la función foldr también podría considerarse el primer argumento del resultado foldr!