Ley para el tipo [[a]] -> ([a], [a])

8

Estoy tratando de hacer esta pregunta desde mi tarea:

Dado arbitrario foo :: [[a]] -> ([a], [a]), escriba una ley que foosatisfaga la función , involucrando mapen listas y pares.

Algún contexto: soy un estudiante de primer año que toma un curso de programación funcional. Si bien el curso es bastante introductorio, el profesor ha mencionado muchas cosas fuera del programa de estudios, entre los cuales se encuentran los teoremas gratuitos. Entonces, después de intentar leer el documento de Wadler, calculé que concat :: [[a]] -> [a]la ley map f . concat = concat . map (map f)parece relevante para mi problema, ya que debemos tener foo xss = (concat xss, concat' xss)dónde concaty concat'cuáles son las funciones de tipo [[a]] -> [a]. Entonces foosatisfacebimap (map f, map g) . foo = \xss -> ((fst . foo . map (map f)) xss, (snd . foo . map (map g)) xss) .

Esta "ley" ya parece demasiado larga para ser correcta, y tampoco estoy seguro de mi lógica. Entonces pensé en usar un generador de teoremas gratis en línea , pero no entiendo qué lift{(,)}significa:

forall t1,t2 in TYPES, g :: t1 -> t2.
 forall x :: [[t1]].
  (f x, f (map (map g) x)) in lift{(,)}(map g,map g)

lift{(,)}(map g,map g)
  = {((x1, x2), (y1, y2)) | (map g x1 = y1) && (map g x2 = y2)}

¿Cómo debo entender esta salida? ¿Y cómo debo derivar la ley para la función foocorrectamente?

haskell free-theorem Jingjie YANG
fuente
55
Creo que esto dice eso(\(a,b) -> (map f a, map f b)) . foo = foo . map (map f)
AJFarmar

Respuestas:

4

Si R1y R2son relaciones (digamos, R_ientre A_iy B_i, con i in {1,2}), entonces lift{(,)}(R1,R2)son los pares de relaciones "levantadas", entre A1 * A2y B1 * B2, con *denotar el producto (escrito(,) en Haskell).

En la relación elevada, dos pares (x1,x2) :: A1*A2y (y1,y2) :: B1*B2están relacionados si y solo si x1 R1 y1y x2 R2 y2. En su caso, R1y R2son funciones map g, map g, el levantamiento también se convierte en una función:y1 = map g x1 && y2 = map g x2 .

Por lo tanto, el generado

(f x, f (map (map g) x)) in lift{(,)}(map g,map g)

medio:

fst (f (map (map g) x)) = map g (fst (f x))
AND
snd (f (map (map g) x)) = map g (snd (f x))

o, en otras palabras:

f (map (map g) x) = (map g (fst (f x)), map g (snd (f x)))

que escribiría como, usando Control.Arrow:

f (map (map g) x) = (map g *** map g) (f x)

o incluso, en estilo sin puntos:

f . map (map g) = (map g *** map g) . f

Esto no es una sorpresa, ya que fse puede escribir como

f :: F a -> G a
where F a = [[a]]
      G a = ([a], [a])

y F, Gson funtores (en Haskell tendríamos que utilizar una newtypepara definir una instancia funtor, pero lo que omitiremos, ya que es irrelevante). En este caso común, el teorema libre tiene una forma muy agradable: para cada g,

f . fmap_of_F g = fmap_of_G g . f

Esta es una forma muy agradable, llamada naturalidad ( fpuede interpretarse como una transformación natural en una categoría adecuada). Tenga en cuenta que los dosf s anteriores en realidad se instancian en tipos separados, por lo que los tipos están de acuerdo con el resto.

En su caso específico, dado F a = [[a]]que es la composición del []functor consigo mismo, por lo tanto, como era de esperar, obtenemosfmap_of_F g = fmap_of_[] (fmap_of_[] g) = map (map g) .

En cambio, G a = ([a],[a])es la composición de los functores []y H a = (a,a)(técnicamente, el functor diagonal compuesto con el functor del producto). Tenemos fmap_of_H h = (h *** h) = (\x -> (h x, h x)), de la cual fmap_of_G g = fmap_of_H (fmap_of_[] g) = (map g *** map g).

chi
fuente
Buena explicación! Solo una pregunta: cuando dices "por cada g", ¿tiene que ser total o estricto, o no hay restricciones?
Jingjie YANG
1
@JingjieYANG Sí, hay algunas restricciones si usamos Haskell. La mayoría de los resultados como este se realizan en un sistema de tipo puro donde cada uno termina (por lo tanto, es total). En Haskell, si no recuerdo mal, ya que no tenemos terminación, necesitamos un gtotal. Del mismo modo, dado que tenemos seqque exigir gque seamos estrictos. No estoy 100% seguro de las restricciones exactas, pero creo que deberían serlo. Sin embargo, no recuerdo dónde leí sobre eso, probablemente en la página del generador de teoremas gratuito hay algo de información.
chi
¿No está Control.Arrow (***) en las tuplas un poco fuera de estilo, a favor de Data.Bifunctor (bimap)? ¿Alguna objeción a una edición para cambiar a esta última?
Joseph Sible-Reinstate Monica
2
@ JosephSible-ReinstateMonica No tengo idea. Creo que es un poco como mapvs fmap. Las personas continúan usando, mapya que hace obvio que estamos tratando con listas (y no con otro functor). Del mismo modo, (***)solo funciona en pares (y no en otros bifunctores). Probablemente lo estoy usando principalmente por su inflexibilidad, ya que en matemáticas tendemos a escribir f \times gpara aplicar el bifunctor del producto. Quizás también bimapdebería tener su variante infija, como <$>es una variante para fmap.
chi
1
Si bien es cierto que (***)es más específico bimapque porque solo funciona en pares en lugar de bifunctores arbitrarios, también es cierto que bimapes más específico (***)que porque solo funciona en funciones en lugar de en flechas arbitrarias. Re infix, eso no sería lo mismo para bimapy fmap, ya que bimaptoma 3 parámetros y fmapsolo toma 2.
Joseph Sible-Reinstate Monica
2

Lo mismo que la respuesta de @ chi con menos ceremonia:

No importa si cambia los as a bs antes o después de la función, obtendrá lo mismo (siempre que use algo fmapsimilar para hacerlo).

Para cualquier f: a -> b,

    [[a]] -------------> [[b]]
      El | (map.map) f |
      El | El |
     Foo Foo
      El | El |
      vv
    ([a], [a]) ---------> ([b], [b])
              bimap ff

conmuta.
luqui
fuente