haskell - Comonadicamente encontrando todas las formas de enfocarse en una cuadrícula

zipper

Question

Esta pregunta ya tiene una respuesta aquí:

• Escribiendo cojoin o cobind para la cuadrícula tridimensional tipo 3 respuestas

{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE DeriveFunctor #-}
{-# LANGUAGE DeriveTraversable #-}
import Control.Comonad
import Data.Functor.Reverse
import Data.List (unfoldr)

Primero algún contexto (ja ja). Tengo una zipper sobre las listas no vacías.

data LZipper a = LZipper (Reverse [] a) a [a]
    deriving (Eq, Ord, Show, Read, Functor, Foldable, Traversable)

mkZipper :: a -> [a] -> LZipper a
mkZipper = LZipper (Reverse [])

Puede avanzar en cualquier dirección a lo largo de la cremallera, pero podría caerse del extremo.

fwd, bwd :: LZipper a -> Maybe (LZipper a)
fwd (LZipper _ _ []) = Nothing
fwd (LZipper (Reverse xs) e (y:ys)) = Just $ LZipper (Reverse (e:xs)) y ys
bwd (LZipper (Reverse []) _ _) = Nothing
bwd (LZipper (Reverse (x:xs)) e ys) = Just $ LZipper (Reverse xs) x (e:ys)

Duplicar una cremallera le muestra todas las formas en que podría mirarlo, con el enfoque en la forma en que lo está viendo actualmente.

instance Comonad LZipper where
    extract (LZipper _ x _) = x
    duplicate z = LZipper (Reverse $ unfoldr (step bwd) z) z (unfoldr (step fwd) z)
        where step move = fmap (/y -> (y, y)) . move

Por ejemplo:

ghci> duplicate (mkZipper ''a'' "bc")
LZipper (Reverse [])
        (LZipper (Reverse "") ''a'' "bc")
        [LZipper (Reverse "a") ''b'' "c",LZipper (Reverse "ba") ''c'' ""]
-- Abc -> *Abc* aBc abC

ghci> fmap duplicate (fwd $ mkZipper ''a'' "bc")
Just (LZipper (Reverse [LZipper (Reverse "") ''a'' "bc"])
              (LZipper (Reverse "a") ''b'' "c")
              [LZipper (Reverse "ba") ''c'' ""])
-- aBc -> Abc *aBc* abC

(Estoy usando mayúsculas y asteriscos para indicar el punto focal de la cremallera).

Estoy tratando de trabajar con grillas de dos dimensiones con un enfoque, representado como una cremallera de cremalleras. Cada cremallera interior es una fila de la rejilla. Mi objetivo final es encontrar caminos a través de una cuadrícula saltando de vecino a vecino.

Moverse a través de la cuadrícula mantiene el invariante de que todas las filas están enfocadas en el mismo índice. Esto hace que sea fácil concentrarse en cualquiera de sus vecinos.

type Grid a = LZipper (LZipper a)

up, down, left, right :: Grid a -> Maybe (Grid a)
up = bwd
down = fwd
left = traverse bwd
right = traverse fwd

extractGrid :: Grid a -> a
extractGrid = extract . extract
mkGrid :: (a, [a]) -> [(a, [a])] -> Grid a
mkGrid (x, xs) xss = mkZipper (mkZipper x xs) $ map (uncurry mkZipper) xss

Ejemplos:

ghci> let myGrid = mkGrid (''a'', "bc") [(''d'', "ef"), (''g'', "hi")]
ghci> myGrid
LZipper (Reverse [])
        (LZipper (Reverse "") ''a'' "bc")
        [LZipper (Reverse "") ''d'' "ef",LZipper (Reverse "") ''g'' "hi"]
-- +-------+ 
-- | A b c |
-- | d e f |
-- | g h i |
-- +-------+

ghci> return myGrid >>= right >>= down
Just (LZipper (Reverse [LZipper (Reverse "a") ''b'' "c"])
              (LZipper (Reverse "d") ''e'' "f")
              [LZipper (Reverse "g") ''h'' "i"])
-- +-------+ 
-- | a b c |
-- | d E f |
-- | g h i |
-- +-------+

Lo que quiero es el equivalente del LZipper de LZipper para cuadrículas: una función que toma una cuadrícula y produce una cuadrícula de todas las formas en que podría mirar la cuadrícula, con el enfoque en la forma actual en que lo está viendo.

duplicateGrid :: Grid a -> Grid (Grid a)

Lo que estoy esperando:

duplicateGrid myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | a B c | | a b C | |
| * d e f * | d e f | | d e f | |
| * g h i * | g h i | | g h i | |
| ********* +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | a b c | | a b c | | a b c | |
| | D e f | | d E f | | d e F | |
| | g h i | | g h i | | g h i | |
| +-------+ +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | a b c | | a b c | | a b c | |
| | d e f | | d e f | | d e f | |
| | G h i | | g H i | | g h I | |
| +-------+ +-------+ +-------+ |
+-------------------------------+

Intenté duplicateGrid = duplicate . duplicate duplicateGrid = duplicate . duplicate Esto tiene el tipo correcto, pero (asumiendo que interpreté la salida del show correctamente, lo cual probablemente no lo hice) solo me da cuadrículas enfocadas en algún lugar de la primera columna:

(duplicate . duplicate) myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | a b c | | a b c | |
| * d e f * | D e f | | d e f | |
| * g h i * | g h i | | G h i | |
| ********* +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
| +-------+ +-------+ +-------+ |
| | A b c | | a b c | | a b c | |
| | d e f | | D e f | | d e f | |
| | g h i | | g h i | | G h i | |
| +-------+ +-------+ +-------+ |
+-------------------------------+

También probé duplicateGrid = duplicate . fmap duplicate duplicateGrid = duplicate . fmap duplicate . Suponiendo una vez más que soy capaz de interpretar la salida del show , esto me dio algo que contenía las cuadrículas incorrectas y tenía los enfoques de las filas desalineados, de modo que al moverte hacia abajo también te moverías:

(duplicate . fmap duplicate) myGrid
+-------------------------------+
| ********* +-------+ +-------+ |
| * A b c * | D e f | | G h i | |
| * a B c * | d E f | | g H i | |
| * a b C * | d e F | | g h I | |
| ********* +-------+ +-------+ |
| +-------+ ********* +-------+ |
| | A b c | * D e f * | G h i | |
| | a B c | * d E f * | g H i | |
| | a b C | * d e F * | g h I | |
| +-------+ ********* +-------+ |
| +-------+ +-------+ ********* |
| | A b c | | D e f | * G h i * |
| | a B c | | d E f | * g H i * |
| | a b C | | d e F | * g h I * |
| +-------+ +-------+ ********* |
+-------------------------------+

Esto parece que sería una pregunta fácil para los que saben, pero está haciendo que mi cabeza gire. Supongo que podría manejar manualmente una función que llama up , down , left y right , pero siento que la maquinaria común debería poder hacerlo por mí. ¿Cuál es la implementación correcta de duplicateGrid ?

Answer 1

Así que hay un comonad estrechamente relacionado que puede ayudarte a guiarte. Tenemos:

newtype MC m a = MC { unMC :: m -> a }

instance Monoid m => Comonad (MC m) where
    extract (MC f) = f mempty
    duplicate (MC f) = MC (/x -> MC (/y -> f (x <> y)))

instance Functor (MC m) where
    fmap f (MC g) = MC (f . g) 

Entonces, una matriz bidireccionalmente infinita sería MC (Sum Integer) a y una cuadrícula bidireccionalmente infinita sería MC (Sum Integer, Sum Integer) a . Y, por supuesto, MC m (MC na) es isomorfo a MC (m,n) a través del curry.

En cualquier caso, su función de cuadrícula duplicada deseada sería análoga (ignorando las envolturas de tipo nuevo y el curry) a:

duplicateGrid g x y dx dy = g (x + dx) (y + dy)

duplicate para la matriz 1D se ve así:

duplicate f x y = f (x+y)

Así que duplicate . duplicate duplicate . duplicate es:

(duplicate . duplicate) f x y z 
    = duplicate (duplicate f) x y z
    = duplicate f (x+y) z
    = f (x + y + z)

No es lo que se quiere. ¿Cómo se fmap duplicate ?

fmap duplicate f x y z = f x (y + z)

Está claro que hacer duplicate nuevo nos dará lo mismo que duplicate . duplicate duplicate . duplicate (que debería ser una ley de comuna). Sin embargo, esto es un poco más prometedor. Si fmap dos fmap s ...

fmap (fmap duplicate) f x y z w
    = fmap duplicate (f x) y z w
    = f x y (z + w)

Ahora si hiciéramos el duplicate obtendríamos

(duplicate . fmap (fmap duplicate)) f x y z w = f (x+y) (z+w)

Pero esto todavía está mal. Cambiando nombres de variables, su f (x+y) (dx + dy) . Entonces, necesitamos algo para intercambiar las dos variables internas ... El nombre de la teoría de categorías para lo que queremos es una ley distributiva. El nombre de Haskell es Traversable . ¿Cómo sequenceA ve la sequenceA para las funciones (las funciones de un funtor de Applicative y, de hecho, una Monad , la mónada del Reader )? El tipo lo dice todo.

sequenceA :: (a -> b -> c) -> (b -> a -> c)
sequenceA f x y = f y x 

Así que finalmente:

fmap sequenceA g x y z = g x z y

(duplicate . fmap (fmap duplicate) . fmap sequenceA) g x y dx dy
    = (duplicate . fmap (fmap duplicate)) g x dx y dy
    = g (x + dx) (y + dy)

No he probado el código análogo, así que no sé si funciona, pero las matemáticas dicen que debería.

Answer 2

El problema fundamental con el que se encuentra es que las cremalleras no admiten de manera nativa estructuras 2-d . La respuesta es excelente (la otra respuesta es básicamente su definición de Grid ) y lo alentaría a que la leyera, pero lo esencial es que las cremalleras identifican los elementos con los caminos para llegar allí y en un espacio bidimensional, tal identificación es Es problemático porque hay muchos caminos para llegar a un punto.

Por lo tanto, notará que mientras sus funciones de up y down para Grid s se definieron completamente en términos de Cremalleras, tuvo que usar la maquinaria de Traversable para definir la left y la right . Esto también significa que la left y la right no disfrutan de las mismas propiedades de rendimiento como up y down ya que estás "en contra del grano", por así decirlo.

Dado que su instancia de Comonad se definió solo mediante las funciones de cremallera, solo puede duplicate en la dirección definida por su cremallera, es decir, fwd y bwd (y por extensión up y down ).

Edit : Después de pensar un poco más, creo que su enfoque será fundamentalmente problemático. He conservado mi texto original a continuación, pero hay un problema más evidente.

Si intentas atravesar las cremalleras como si fueran como cualquier otra estructura 2-d, seguirás obteniendo Nothing con tu duplicate . Observemos qué sucede si realmente intenta utilizar las funciones up, down, left, right en el duplicate (mkZipper ''a'' "bc") aparentemente no problemático duplicate (mkZipper ''a'' "bc") .

*Main> let allRows = duplicate $ mkZipper ''a'' "bc"
*Main> down allRows -- This is fine since we''re following the zipper normally
Just (LZipper (Backwards [LZipper (Backwards "") ''a'' "bc"]) (LZipper (Backwards "a") ''b'' "c") [LZipper (Backwards "ba") ''c'' ""])
*Main> right allRows
Nothing -- That''s bad...
*Main> down allRows >>= right
Nothing -- Still nothing

Moverse hacia la right y hacia la left requiere (como usted nota debidamente con su mención del invariante) que cada una de sus sub-cremalleras es homogénea en su estructura, de lo contrario, la traverse fallará prematuramente. Esto significa que si realmente quieres usar la left y la right , la única forma en que esto va a jugar bien con el duplicate es si usas el duplicate más uniforme posible.

duplicate z @ (LZipper left focus right) = 
    LZipper (fmap (const z) left) z (fmap (const z) right)

La alternativa es usar solo las funciones que vienen con la cremallera. Eso significa solo usar fwd y bwd , y luego extract el foco y continuar usando fwd y bwd para obtener lo mismo que a left y right . Por supuesto, eso significa renunciar a la habilidad de decir "justo en el momento" y "abajo que en la derecha", pero como ya hemos visto, las cremalleras no juegan bien con múltiples caminos.

Ahora revisemos sus intuiciones sobre la mejor manera de interpretar lo que estaba sucediendo con el duplicate . duplicate $ myGrid duplicate . duplicate $ myGrid . Una plaza bonita no es realmente la mejor forma de pensar sobre lo que está pasando (y verá por qué, si se limita a extract y fwd y bwd ).

*Main> let allRows = duplicate . duplicate $ myGrid
*Main> fwd $ extract allRows -- Makes sense
Just ...
-- This *should* be the bottom-left of the grid
*Main> let bottomLeft = extract <$> fwd allRows >>= fwd
*Main> bottomLeft >>= fwd
Nothing -- Nope!
*Main> bottomLeft >>= bwd
Just ... -- Wait a minute...

En realidad tenemos una estructura irregular.

+---------------------------------------------------+
|                     ********* +-------+ +-------+ |
|                     * A b c * | a b c | | a b c | |
|                     * d e f * | D e f | | d e f | |
|                     * g h i * | g h i | | G h i | |
|                     ********* +-------+ +-------+ |
|           +-------+ +-------+ +-------+           |
|           | A b c | | a b c | | a b c |           |
|           | d e f | | D e f | | d e f |           |
|           | g h i | | g h i | | G h i |           |
|           +-------+ +-------+ +-------+           |
| +-------+ +-------+ +-------+                     |
| | A b c | | a b c | | a b c |                     |
| | d e f | | D e f | | d e f |                     |
| | g h i | | g h i | | G h i |                     |
| +-------+ +-------+ +-------+                     |
+---------------------------------------------------+

Los cuadrados dentro de esta estructura irregular tampoco son en realidad cuadrados, también serán irregulares. De manera equivalente, se podría pensar que fwd va en diagonal. O simplemente suelte las cremalleras para estructuras en 2-d en total.

En mi experiencia, las cremalleras realmente funcionan mejor cuando se combinan con cosas parecidas a árboles. No me sorprendería si un experto en Haskell pudiera encontrar una forma de usar cremalleras y toda la actualización / acceso a la bondad que vienen con ellos para cosas como gráficos cíclicos o simplemente DAG antiguos, pero no puedo pensar en ninguna. fuera de la parte superior de mi cabeza magra :).

Así que, moraleja de la historia, las cremalleras son un dolor de cabeza para las estructuras 2-d. (Pensamiento ocioso: tal vez las lentes podrían ser interesantes?)

Para los curiosos, mi enfoque a continuación solo funciona si se tiene en cuenta la irregularidad de la estructura con la que estamos tratando; eso es fwd dos veces y luego extraerlo te dará el equivalente a lo que OP quiere en la esquina inferior derecha de su cuadrícula, no en el lado inferior izquierdo.

Original :

Entonces, lo que necesita es alguna forma de cambiar entre su duplicate basado en la cremallera y su duplicado basado en el desplazamiento. La forma más fácil es tomar su función duplicate que ya ha escrito y simplemente agregar una traverse en el medio.

duplicateT :: Traversable t => t (LZipper a) -> LZipper (t (LZipper a))
duplicateT z = LZipper (Backwards $ unfoldr (step bwd) z) z (unfoldr (step fwd) z)
    -- Everything''s the exact same except for that extra traverse
    where step move = fmap (/y -> (y, y)) . (traverse move)

Ahora que tenemos un duplicateT más general, podemos deshacernos de una duplicación de código desagradable redefiniendo el duplicate en su instancia de Comonad para que sea:

-- requires import Data.Functor.Identity
duplicate = fmap runIdentity (duplicate'' (Identity z))

Entonces lo siguiente te da lo que quieres

duplicateGrid = duplicate . duplicateT

O si desea cambiar el orden de las columnas y filas, puede hacer lo contrario.

Nota: sería aún más agradable si Haskell le permitiera definir de forma nativa las restricciones de tipo en las clases de tipos para que pueda tener diferentes instancias de Comonad (quizás todas ellas mediadas por newtype ) para su LZipper que cambie la dirección de su duplicate . El problema es que querrías algo como la instance Comonad LZipper (LZipper a) where ... o el nuevo tipo equivalente que simplemente no puedes escribir en Haskell. Posiblemente podría hacer algo como this con familias de tipos, pero sospecho que probablemente sea excesivo para este caso en particular.

Edición : De hecho, ni siquiera necesita duplicateT LZipper si da la instancia de Applicative adecuada para LZipper .

instance Applicative LZipper where
    pure x = LZipper (Backwards (repeat x)) x (repeat x)
    (LZipper leftF f rightF) <*> (LZipper left x right) = LZipper newLeft (f x) newRight
      where
        newLeft = (Backwards (zipWith ($) (forwards leftF) (forwards left)))
        newRight = (zipWith ($) rightF right)

Ahora simplemente toma el duplicate original que tenías antes y usa la traverse .

duplicateGrid = duplicate . (traverse duplicate)

Answer 3

Es un problema que estamos tratando de componer Grid consigo mismo, porque esta configuración nos brinda demasiadas formas incorrectas de implementar un duplicate con el tipo correcto. Es útil considerar el caso general en el que las comillas compuestas no son necesariamente las mismas.

Supongamos que tenemos comillas f y g . El tipo de duplicate convierte en:

duplicate :: f (g a) -> f (g (f (g a)))

Podemos obtener lo siguiente únicamente utilizando las instancias de Comonad :

duplicate . fmap duplicate :: f (g a) -> f (f (g (g a)))

De esto se hace evidente que necesitamos intercambiar f y g en el medio.

Hay una clase de tipo llamada Distributive que tiene el método que queremos.

class Functor g => Distributive g where
    distribute :: Functor f => f (g a) -> g (f a)

En particular, necesitamos implementar Distributive g , y luego duplicate para el comonad compuesto se puede implementar como:

duplicate = fmap distribute . duplicate . fmap duplicate

Sin embargo, la documentación en Distributive dice que los valores de g deben tener exactamente la misma forma, por lo que podemos comprimir un número arbitrario de copias sin pérdida de información.

Para ilustrar esto, si Vec na es un vector de tamaño n , entonces distribute :: [Vec na] -> Vec n [a] es solo una transposición de matriz. Es necesario fijar el tamaño hacia abajo del vector interior de antemano, porque la transposición en una matriz "irregular" debe eliminar algunos elementos, y eso no es un comportamiento legal. Las corrientes infinitas y las cremalleras también se distribuyen bien, ya que también tienen un solo tamaño posible.

Zipper no es un Distributive legal porque Zipper contiene valores con contextos de diferentes tamaños. Aún así, podemos implementar una distribución inadecuada que supone tamaños de contexto uniformes.

A continuación, implementaré el duplicate de Grid en términos de distribución inadecuada para las listas subyacentes.

Alternativamente, uno podría simplemente enrollar sus mangas e implementar una función de transposición en Zipper (Zipper a) directamente. De hecho, hice esto, pero me dio un dolor de cabeza y estoy lejos de estar seguro de que es correcto. Es mejor hacer los tipos tan generales como sea posible, para reducir el espacio de posibles implementaciones, por lo que hay menos espacio para errores.

Voy a omitir Reverse para reducir el ruido sintáctico; Espero que me disculpes.

{-# language DeriveFunctor #-}

import Control.Comonad
import Data.List
import Control.Monad

data Zipper a = Zipper [a] a [a] deriving (Eq, Show, Functor)

lefts, rights :: Zipper a -> [a]
lefts  (Zipper ls _ _) = ls
rights (Zipper _ _ rs) = rs

bwd :: Zipper a -> Maybe (Zipper a)
bwd (Zipper [] _ _) = Nothing
bwd (Zipper (l:ls) a rs) = Just $ Zipper ls l (a:rs)

fwd :: Zipper a -> Maybe (Zipper a)
fwd (Zipper _ _ []) = Nothing
fwd (Zipper ls a (r:rs)) = Just $ Zipper (a:ls) r rs

instance Comonad Zipper where
  extract (Zipper _ a _) = a
  duplicate z =
    Zipper (unfoldr (fmap (join (,)) . bwd) z) z (unfoldr (fmap (join (,)) . fwd) z)

Podemos distribuir listas si sabemos de antemano su longitud. Dado que las listas de Haskell pueden ser infinitas, debemos medir la longitud con posiblemente infinitos naturales perezosos. Una solución alternativa para medir la longitud sería utilizar una lista "guía" a lo largo de la cual podamos comprimir otras listas. Sin embargo, preferiría no asumir en las funciones de distribución que una lista ficticia de este tipo está siempre disponible.

data Nat = Z | S Nat

length'' :: [a] -> Nat
length'' = foldr (const S) Z

distList :: Functor f => Nat -> f [a] -> [f a]
distList Z     fas = []
distList (S n) fas = (head <$> fas) : distList n (tail <$> fas)

Por supuesto, esto falla con las excepciones de tiempo de ejecución si nuestra suposición de longitud es incorrecta.

Podemos distribuir Zipper s distribuyendo sus enfoques y contextos, siempre que sepamos la longitud de los contextos:

distZipper :: Functor f => Nat -> Nat -> f (Zipper a) -> Zipper (f a)
distZipper l r fz = Zipper
  (distList l (lefts <$> fz)) (extract <$> fz) (distList r (rights <$> fz))

Finalmente, podemos duplicar las Grid en la forma en que vimos antes, pero primero tenemos que determinar la forma de las Zipper internas. Como suponemos que todas las Zipper interiores tienen la misma forma, solo miramos la Zipper en el foco:

duplicateGrid :: Grid a -> Grid (Grid a)
duplicateGrid grid@(Zipper _ (Zipper ls _ rs) _) = 
    fmap (distZipper (length'' ls) (length'' rs)) $ duplicate $ fmap duplicate grid

Probar esto (como ya debe haberlo experimentado) es bastante horrible, y todavía no he podido revisar ni siquiera un caso de dos en dos a mano.

Sin embargo, tengo bastante confianza en la implementación anterior, ya que las definiciones están muy limitadas por los tipos.