operator - Aplicación de función Haskell y currying

curry function haskell

Question

Siempre estoy interesado en aprender nuevos idiomas, un hecho que me mantiene alerta y me hace (creo) un mejor programador. Mis intentos de conquistar Haskell van y vienen, dos veces hasta ahora, y decidí que era hora de volver a intentarlo. La tercera vez es el encanto, ¿verdad?

Nop. Releí mis notas antiguas ... y me decepcioné :-(

El problema que me hizo perder la fe la última vez fue fácil: permutaciones de enteros. es decir, de una lista de enteros a una lista de listas, una lista de sus permutaciones:

[int] -> [[int]]

Este es, de hecho, un problema genérico, por lo que reemplazar ''int'' anterior con ''a'', todavía se aplicaría.

De mis notas:

Primero lo codifico por mi cuenta, tengo éxito. ¡Hurra!

Envío mi solución a un buen amigo mío, gurú Haskell, por lo general ayuda a aprender de los gurús, y él me envía esto, lo que me dicen, "expresa el verdadero poder del lenguaje, el uso de instalaciones genéricas para codificar su necesariamente". Todo por ello, recientemente bebí el kool-aid, vamos:

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

Hmm. Vamos a desglosar esto:

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

OK, hasta ahora, muy bien. Me tomó un minuto entender la segunda línea de "ins", pero está bien: coloca la 1ra arg en todas las posiciones posibles en la lista. Guay.

Ahora, para entender el foldr y concatMap. en "Haskell del mundo real", se explicó el DOT ...

(f . g) x

... como una sintaxis más para ...

f (g x) 

Y en el código que el gurú envió, DOT se usó desde un foldr, con la función "ins" como el doblez "colapso":

*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

De acuerdo, ya que quiero entender cómo el GOT usa el DOT, intento la expresión equivalente de acuerdo con la definición del DOT, (f. G) x = f (gx) ...

*Main> concatMap (ins 1 [[2,3]])

<interactive>:1:11:
     Couldn''t match expected type `a -> [b]''
            against inferred type `[[[t]]]''
     In the first argument of `concatMap'', namely `(ins 1 [[2, 3]])''
     In the expression: concatMap (ins 1 [[2, 3]])
     In the definition of `it'': it = concatMap (ins 1 [[2, 3]])

¡¿¡Qué!?! ¿Por qué? OK, verifico la firma de concatMap, y encuentro que necesita una lambda y una lista, pero eso es solo un pensamiento humano; ¿Cómo se las arregla GHC? De acuerdo con la definición de DOT arriba ...

(f.g)x = f(g x), 

... lo que hice fue válido, reemplazable:

(concatMap . ins) x y = concatMap (ins x y)

Rascándose la cabeza ...

*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

Entonces ... La explicación del DOT fue aparentemente demasiado simplista ... El DOT debe ser de alguna manera lo suficientemente inteligente como para entender que de hecho queríamos "ins" para deshacernos del currículum y "comer" el primer argumento, convirtiéndonos así en una función que solo quiere operar en [t] (y "intercalar" con ''1'' en todas las posiciones posibles).

Pero, ¿dónde se especificó esto? ¿Cómo supo GHC hacer esto cuando invocamos?

*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

¿La firma "ins" de alguna manera transmitió esta ... política de "come mi primer argumento"?

*Main> :info ins
ins :: t -> [t] -> [[t]]        -- Defined at b.hs:1:0-2

No veo nada especial: "ins" es una función que toma una "t", una lista de "t", y procede a crear una lista con todas las "intercalaciones". Nada sobre "come tu primer argumento y pruébalo".

Entonces ahí ... estoy desconcertado. Entiendo (¡después de una hora de mirar el código!) Lo que sucede, pero ... Dios todopoderoso ... ¿Quizás GHC hace intentos para ver cuántos argumentos puede "despegar"?

  let''s try with no argument "curried" into "ins",
  oh gosh, boom, 
  let''s try with one argument "curried" into "ins",
  yep, works,
  that must be it, proceed)

De nuevo, yikes ...

Y dado que siempre estoy comparando los idiomas que estoy aprendiendo con lo que ya sé, ¿qué aspecto tendría "ins" en Python?

a=[2,3]
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]

[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

Se honesto, ahora ... ¿qué es más simple?

Quiero decir, sé que soy un novato en Haskell, pero me siento como un idiota ... Mirando 4 líneas de código durante una hora, y terminando asumiendo que el compilador ... intenta varias interpretaciones hasta que encuentra algo que " clics "?

Para citar el arma letal, "soy demasiado viejo para esto" ...

Answer 1

Estás pensando demasiado en este problema. Puedes resolverlo usando un razonamiento ecuacional simple. Probémoslo desde cero:

permute = foldr (concatMap . ins) [[]]

Esto se puede convertir trivialmente en:

permute lst = foldr (concatMap . ins) [[]] lst

concatMap se puede definir como:

concatMap f lst = concat (map f lst)

La forma en que foldr funciona en una lista es (por ejemplo):

-- let lst = [x, y, z]
foldr f init lst
= foldr f init [x, y, z]
= foldr f init (x : y : z : [])
= f x (f y (f z init))

Así que algo así como

permute [1, 2, 3]

se convierte en:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))

Vamos a trabajar a través de la primera expresión:

(concatMap . ins) 3 [[]]
= (/x -> concatMap (ins x)) 3 [[]]  -- definition of (.)
= (concatMap (ins 3)) [[]]
= concatMap (ins 3) [[]]     -- parens are unnecessary
= concat (map (ins 3) [[]])  -- definition of concatMap

Ahora ins 3 [] == [3] , entonces

map (ins 3) [[]] == (ins 3 []) : []  -- definition of map
= [3] : []
= [[3]]

Entonces nuestra expresión original se convierte en:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]]

Vamos a trabajar a través de

(concatMap . ins) 2 [[3]]
= (/x -> concatMap (ins x)) 2 [[3]]
= (concatMap (ins 2)) [[3]]
= concatMap (ins 2) [[3]]     -- parens are unnecessary
= concat (map (ins 2) [[3]])  -- definition of concatMap
= concat (ins 2 [3] : [])
= concat ([[2, 3], [3, 2]] : [])
= concat [[[2, 3], [3, 2]]]
= [[2, 3], [3, 2]]

Entonces nuestra expresión original se convierte en:

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 [[2, 3], [3, 2]]
= (/x -> concatMap (ins x)) 1 [[2, 3], [3, 2]]
= concatMap (ins 1) [[2, 3], [3, 2]]
= concat (map (ins 1) [[2, 3], [3, 2]])
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
          [[1, 3, 2], [3, 1, 2], [3, 2, 1]]]  -- defn of ins
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
   [1, 3, 2], [3, 1, 2], [3, 2, 1]]

Nada mágico aquí. Creo que puede haber estado confundido porque es fácil suponer que concatMap = concat . map concatMap = concat . map , pero este no es el caso. Del mismo modo, puede parecer que concatMap f = concat . (map f) concatMap f = concat . (map f) , pero esto tampoco es cierto. El razonamiento ecuacional te mostrará por qué.

Answer 2

Me gustaría agregar mis dos centavos. La pregunta y la respuesta lo hacen sonar como . es un operador mágico que hace cosas extrañas con la reorganización de llamadas a funciones. Ese no es el caso. . es solo composición de la función. Aquí hay una implementación en Python:

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

Simplemente crea una nueva función que aplica g a un argumento, aplica f al resultado y devuelve el resultado de aplicar f .

Entonces (concatMap . ins) 1 [[2, 3]] está diciendo: crea una función, concatMap . ins concatMap . ins , y aplicarlo a los argumentos 1 y [[2, 3]] . Cuando haces concatMap (ins 1 [[2,3]]) estás diciendo, aplica la función concatMap al resultado de aplicar ins a 1 y [[2, 3]] - completamente diferente, como te imaginaste Mensaje de error horrendo de Haskell.

ACTUALIZACIÓN: Para enfatizar esto aún más. Usted dijo que (f . g) x era otra sintaxis para f (gx) . ¡Esto está mal ! . es solo una función, ya que las funciones pueden tener nombres no alfanuméricos ( >>< , .. , etc., también podrían ser nombres de funciones).

Answer 3

(f . g) x = f (g x)

Esto es verdad. Usted concluyó de eso que

(f . g) x y = f (g x y)

también debe ser cierto, pero ese no es el caso. De hecho, lo siguiente es cierto:

(f . g) x y = f (g x) y

que no es lo mismo

¿Por qué es esto cierto? Bien (f . g) xy es lo mismo que ((f . g) x) y y como sabemos que (f . g) x = f (gx) podemos reducir eso a (f (gx)) y , que es de nuevo lo mismo que f (gx) y .

Entonces (concatMap . ins) 1 [[2,3]] es equivalente a concatMap (ins 1) [[2,3]] . No hay magia pasando aquí.

Otra forma de abordar esto es a través de los tipos:

. tiene el tipo (b -> c) -> (a -> b) -> a -> c , concatMap tiene el tipo (x -> [y]) -> [x] -> [y] , ins tiene escriba t -> [t] -> [[t]] . Entonces, si usamos concatMap como el argumento b -> c y ins como el argumento a a -> b , entonces a convierte en t , b convierte en [t] -> [[t]] y c convierte en [[t]] -> [[t]] (con x = [t] e y = [t] ).

Entonces el tipo de concatMap . ins concatMap . ins es t -> [[t]] -> [[t]] , lo que significa que una función toma una lista de lo que sea y una lista (de lo que quiera) y devuelve una lista de listas (del mismo tipo).