aplicación de función anidada

Question

Es bastante fácil de definir un operador como

(@) :: [x -> y] -> [x] -> [y] 

que tiene una lista de funciones y una lista de entradas y devuelve una lista de salidas. Hay dos maneras obvias para implementar esta:

1. Aplicar la primera función a la primera entrada, la segunda función a la segunda entrada, etc.
2. Aplicar todas las funciones a cada entrada.

Cualquiera de las dos cosas es igualmente trivial de definir. Lo bueno de esto es que ahora se puede hacer algo como

foo :: X -> Y -> Z -> R 

bar :: [X] -> [Y] -> [Z] -> [R] 
bar xs ys zs = [foo] @@ xs @@ ys @@ zs 

Esto generaliza a un número arbitrario de argumentos de la función.

---

Hasta ahora todo bien. Ahora para el problema: ¿Cómo puedo cambiar la firma tipo para @@ que la rúbrica tipo para bar convierte

bar :: [X] -> [Y] -> [Z] -> [[[R]]] 

No es difícil de implementar una función de este tipo; cualquiera de estos lo hará:

bar xs ys zs = map (\ x -> map (\ y -> map (\ z -> foo x y z) zs) ys) zs 
bar xs ys zs = map (\ z -> map (\ y -> map (\ x -> foo x y z) xs) ys) zs 

No soy quisquilloso sobre qué resultado obtengo. Pero no puedo entender cómo ajustar el operador @@ para hacer esto.

---

Una cosa obvia a probar es

(@@) :: [x -> y] -> [x] -> [[y]] 

No es difícil de implementar esto, pero no le ayudará. Ahora usted tiene

[foo] @@ xs :: [[Y -> Z -> R]] 

que no es una entrada válida para @@. No hay una manera obvia de saber cuántos niveles de listas hay que alcanzar para llegar a la función; claramente este enfoque es un callejón sin salida.

He intentado varias otras posibles firmas de tipo, pero ninguna de ellas me acerca a la respuesta. ¿Alguien puede darme una solución o explicar por qué no existe?

Answer 1

¡En realidad, esto no necesita clases de tipos en absoluto! Pierdes un poco de conveniencia al evitar clases de tipo, pero eso es todo.

El punto clave es que, a pesar de reutilizar un único combinador, el polimorfismo permite que el tipo de cada uso sea diferente. Este es el mismo principio detrás de las expresiones de estilo Applicative como f <$> xs <*> ys <*> zs, y el resultado final aquí será similar. Como tal, lo haremos por cualquier Functor, no solo listas.

La diferencia entre esto y la versión Applicative es que profundizamos en los Functor s anidados en cada paso. El polimorfismo necesario requiere flexibilidad en la capa más interna, por lo que utilizaremos un truco de continuación-ish donde el resultado de cada combinador es una función que acepta una transformación para usar en la capa más interna.

Necesitaremos dos operadores, uno que inicie la cadena y otro que lo continúe incrementalmente. A partir de este último:

(@@) :: (Functor f) => (((a -> b) -> f c) -> r) -> f a -> (b -> c) -> r 
q @@ xs = \k -> q (\f -> k . f <$> xs) 

Esto toma un nuevo argumento a la derecha, y la expresión en curso a la izquierda. El resultado toma una función k, que especifica qué hacer para obtener el resultado final. k se combina con lo que sea que la expresión en progreso ya tenga, y ambos se asignan sobre el nuevo argumento. Esto es intrincado, pero debería resultarle familiar a cualquiera que haya tomado el código de estilo CPS.

(<@) :: (Functor f, Functor g) => f (a -> b) -> g a -> (b -> c) -> f (g c) 
fs <@ xs = (<$> fs) @@ xs 

La cadena se inicia con sólo el mapeo de todo lo demás sobre el primer argumento.

A diferencia del caso Applicative más simple, también necesitamos finalizar explícitamente la cadena. Al igual que con la mónada Cont, la forma más sencilla de hacerlo es aplicar el resultado a la función de identidad.Vamos a darle un nombre que útiles:

nested = ($ id) 

Ahora, podemos hacer cosas como esta:

test2 :: [X -> Y -> R] -> [X] -> [Y] -> [[[R]]] 
test2 fs xs ys = nested (fs <@ xs @@ ys) 

test3 :: [X -> Y -> Z -> R] -> [X] -> [Y] -> [Z] -> [[[[R]]]] 
test3 fs xs ys zs = nested (fs <@ xs @@ ys @@ zs) 

No es tan bonita como la versión de la clase de tipo, pero funciona.

Answer 2

Ya ha visto por qué esto es problemático. Su función (@@) se aplica a entradas de diferentes tipos (p. Ej. [x->y], [[x -> y]], etc. Esto significa que su firma de tipo @@ es demasiado restrictiva; necesitará agregar un poco de polimorfismo para hacerlo más general suficiente para usarlo con anidados listas. Dado que Haskell implementa polimorfismo con clases de tipos, esa es una buena dirección para intentarlo.

Como ocurre, con este problema si conoce el tipo de LHS, puede determinar de forma única tanto el RHS como el resultado. entrada tiene tipo [a->b], el RHS debe ser [a] y el resultado debe ser [[b]]. Esto se puede simplificar a una entrada de a->b, RHS de [a] y resultado de [b].Como el LHS determina los otros parámetros y resultados, podemos usar fundeps o familias de tipos para representar los otros tipos.

{-# LANGUAGE TypeFamilies, UndecidableInstances #-} 

class Apply inp where 
    type Left inp :: * 
    type Result inp :: * 
    (@@) :: inp -> [Left inp] -> [Result inp] 

Ahora que tenemos una clase tipo, podemos hacer que la instancia obvia para una función:

instance Apply (a -> b) where 
    type Left (a -> b) = a 
    type Result (a -> b) = b 
    (@@) = map 

La instancia de la lista no es tan malo tampoco:

instance Apply f => Apply [f] where 
    type Left [f] = Left f 
    type Result [f] = [Result f] 
    l @@ r = map (\f -> f @@ r) l 
    -- or map (@@ r) l 

Ahora nuestro método de clase @@ debería funcionar con listas arbitrariamente profundas. Aquí hay algunas pruebas:

*Main> (+) @@ [1..3] @@ [10..13] 
[[11,12,13,14],[12,13,14,15],[13,14,15,16]]'s 

let foo :: Int -> Char -> Char -> String 
    foo a b c = b:c:show a 

*Main> foo @@ [1,2] @@ "ab" @@ "de" 
[[["ad1","ae1"],["bd1","be1"]],[["ad2","ae2"],["bd2","be2"]]] 

Es posible que desee ver en la aplicación printf para más inspiración.

Editar: Poco después de publicar esto, me di cuenta de que se podía generalizar el tipo de contenedor en mi clase de ApplyList a un Applicative, a continuación, utilizar la instancia aplicativo en lugar de mapa. Esto permitiría tanto la lista regular como el comportamiento ZipList.