Comonadisch finden alle Möglichkeiten, auf ein Gitter zu konzentrieren

Question

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

Zuerst einige Kontext (ha ha). Ich habe eine zipper über nicht leere Listen.

Sie können in beide Richtungen entlang des Reißverschlusses treten, aber Sie könnten vom Ende fallen.

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) 

einen Reißverschluss Duplizierung zeigt Ihnen alle Möglichkeiten, wie man es, mit dem Fokus auf den Weg, um es Sie suchen zur Zeit aussehen könnte.

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 

Zum Beispiel:

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 

(Ich bin mit Kapitellen und Sternchen in den Mittelpunkt des Reißverschlusses, um anzuzeigen.)

---

Ich versuche, mit zwei zu arbeiten Raster mit einem Fokus, dargestellt als Reißverschluß. Jeder innere Reißverschluss ist eine Reihe des Gitters. Mein Endziel ist es, Wege durch ein Raster zu finden, indem ich von Nachbarn zu Nachbarn hüpfe.

Beim Verschieben durch das Raster bleibt die Invariante erhalten, dass alle Zeilen auf denselben Index ausgerichtet sind. Dies macht es einfach, sich auf einen Ihrer Nachbarn zu konzentrieren.

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 

Beispiele:

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 | 
-- +-------+ 

Was ich will, ist das Äquivalent von LZipper ‚s duplicate für Grids: eine Funktion, die ein Gitter nimmt und ein Gitter von allen Möglichkeiten, wie Sie an das Netz aussehen könnte , mit dem Fokus auf die aktuelle Weise, die Sie es betrachten.

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

Was ich erwarte:

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 | | 
| +-------+ +-------+ +-------+ | 
+-------------------------------+ 

Ich versuchte duplicateGrid = duplicate . duplicate. Dies hat den richtigen Typen, aber (unter der Annahme, dass ich den show Ausgang richtig interpretiert, die ich wahrscheinlich nicht) es gibt nur ich irgendwo auf der ersten Spalte fokussiert Grids:

(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 | | 
| +-------+ +-------+ +-------+ | 
+-------------------------------+ 

Ich habe auch versucht duplicateGrid = duplicate . fmap duplicate. Unter der Annahme, noch einmal, dass ich von der Interpretation des show Ausgang der Lage bin, gab dies mir etwas, das sowohl die falschen Gitter enthielt und die Schwerpunkte der Reihen versetzt, so dass auch nach unten bewegen Sie sich bewegen würde zusammen:

(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 * | 
| +-------+ +-------+ ********* | 
+-------------------------------+ 

Das fühlt sich an, als ob es eine einfache Frage für diejenigen ist, die Bescheid wissen, aber es bringt meinen Kopf in Wallung. Ich nehme an, ich könnte eine Funktion, die up, down, left und right ruft Call-Handkurbeln, aber ich fühle mich wie die comonadic Maschinerie sollte es für mich tun können. Was ist die korrekte Implementierung von duplicateGrid?

Answer 1

Es ist ein bisschen ein Problem hier, dass wir versuchen, Grid mit sich selbst zu komponieren, weil dieses Setup uns zu viele falsche Wege gibt, um eine duplicate mit dem richtigen Typ zu implementieren. Es ist nützlich, den allgemeinen Fall zu betrachten, in dem die zusammengesetzten Komonaden nicht notwendigerweise gleich sind.

Angenommen, wir haben f und g comonads. Die Art der duplicate wird:

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

Daraus wird deutlich, dass wir f und g in der Mitte tauschen müssen:

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

wir die folgenden ausschließlich mit den Comonad Instanzen bekommen.

Es gibt eine Typklasse namens Distributive, die die von uns gewünschte Methode hat.

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

Insbesondere müssen wir Distributive g, implementieren und dann duplicate für das zusammengesetzt comonad kann realisiert werden:

duplicate = fmap distribute . duplicate . fmap duplicate 

jedoch die Dokumentation in Distributive sagt, dass die Werte von g die genauen haben muss gleiche Form, so dass wir beliebig viele Kopien ohne Informationsverlust zusammenfügen können.

Um dies zu veranschaulichen, wenn Vec n a ist ein n -größe Vektor, dann distribute :: [Vec n a] -> Vec n [a] ist nur Matrix-Transposition. Es ist notwendig, die Down-Größe des inneren Vektors vorher festzulegen, da die Transposition auf einer "zerfetzten" Matrix einige Elemente fallen lassen muss, und das ist kein gesetzmäßiges Verhalten. Unendliche Ströme und Reißverschlüsse verteilen sich auch gut, da sie auch nur eine mögliche Größe haben.

Zipper ist kein gesetzliches Distributive, weil Zipper Werte mit unterschiedlich großen Kontexten enthält. Dennoch können wir eine falsche Verteilung implementieren, die einheitliche Kontextgrößen voraussetzt.

Im Folgenden werde ich implementieren duplicate für Grid in Bezug auf die falsche Verteilung für die zugrunde liegenden Listen.

Alternativ könnte man einfach die Ärmel hochkrempeln und eine Umsetzfunktion direkt auf Zipper (Zipper a) umsetzen. Ich tat das tatsächlich, aber es gab mir Kopfschmerzen und ich bin weit davon entfernt, zuversichtlich zu sein, dass es korrekt ist. Es ist besser, die Typen so allgemein wie möglich zu machen, um den Raum möglicher Implementierungen einzugrenzen, so dass weniger Platz für Fehler ist.

Ich werde Reverse weglassen, um syntaktisches Rauschen zu reduzieren; Ich hoffe, Sie entschuldigen mich.

{-# 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) 

Wir können Listen verteilen, wenn wir ihre Länge vorher wissen. Da Haskells Listen unendlich sein können, sollten wir Längen mit möglicherweise unendlichen faulen Naturmenschen messen. Eine alternative Lösung zur Längenmessung wäre die Verwendung einer "Guide" -Liste, entlang derer wir andere Listen zippen können. Allerdings würde ich in den Verteilungsfunktionen nicht davon ausgehen, dass eine solche Dummy-Liste immer verfügbar ist.

Natürlich scheitert das mit Laufzeitausnahmen, wenn unsere Längenannahme falsch ist.

Wir Zipper s verteilen durch ihre Schwerpunkte und Kontexte zu verteilen, vorausgesetzt, dass wir die Längen der Zusammenhänge kennen:

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)) 

Schließlich haben wir Grid s in der Art und Weise duplizieren können wir zuvor gesehen haben, aber zuerst wir muss die Form des inneren Zipper s bestimmen. Da wir davon ausgehen, dass alle inneren Zipper s die gleiche Form haben, schauen wir erst am Zipper im Fokus:

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

Testing dies (wie Sie bereits erfahren haben muss) ziemlich schrecklich ist, und ich habe noch nicht herumgekommen, um sogar einen Zwei-mal-Zwei-Fall von Hand zu überprüfen.

Dennoch bin ich ziemlich zuversichtlich in der obigen Implementierung, da die Definitionen stark durch die Typen eingeschränkt sind.

Answer 2

Es gibt also eine eng verwandte comonad, die Ihnen helfen kann.Wir haben:

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) 

So eine in zwei Richtungen unendliche Reihe MC (Sum Integer) a sein würde und ein in zwei Richtungen unendlichen Gitter würden MC (Sum Integer, Sum Integer) a sein. Und natürlich ist MC m (MC n a) isomorph zu MC (m,n) a über Curry.

Auf jeden Fall die gewünschte doppelte Gitterfunktion analog wäre (ohne Berücksichtigung newtype Wrapper und Striegeln) zu:

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

duplicate für die 1D-Array wie folgt aussieht:

duplicate f x y = f (x+y) 

So duplicate . duplicate ist :

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

Nicht, was gewünscht wird. Was bedeutet fmap duplicate wie folgt aussehen:

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

Es ist klar, duplicate wieder tun wird uns die gleiche Sache wie duplicate . duplicate (was es sein sollte, da dies ein comonad Gesetz). Trotzdem ist das ein bisschen vielversprechender. Wenn wir zweifmap s tat ...

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

Wenn wir nun duplicate tat würden wir

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

bekommen Aber das ist immer noch falsch. Ändern von Variablennamen, f (x+y) (dx + dy). Wir brauchen also etwas, um die beiden inneren Variablen zu tauschen ... Der Name der Kategorienlehre für das, was wir wollen, ist ein distributives Gesetz. Der Haskell Name ist Traversable. Wie sieht sequenceA für Funktionen (Funktionen bilden eine Applicative Funktor und in der Tat eine Monad, die Reader Monad) aussehen? Der Typ sagt alles.

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

So endlich:

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) 

Ich habe versucht, nicht tatsächlich den analogen Code, damit ich weiß nicht, ob es funktioniert, aber Mathe sagt es soll.

Answer 3

Das grundlegende Problem, in das Sie geraten, ist das zippers don't natively support 2-d structures. Die Antwort dort ist großartig (die andere Antwort ist im Grunde genau Ihre Definition von Grid) und ich würde Sie ermutigen, es zu lesen, aber das Wesentliche ist, dass Reißverschlüsse Elemente mit Pfaden identifizieren, um dorthin zu gelangen, und in einem 2-d-Raum eine solche Identifikation ist problematisch, weil es viele Wege gibt, um zu einem Punkt zu kommen.

Daher werden Sie feststellen, dass, während die up und down Funktionen für Grid s vollständig in Bezug auf die Reißverschlüsse definiert wurde, Sie Traversable Maschinen zu verwenden, benötigt left und right zu definieren. Dies bedeutet auch, dass left und right nicht die gleichen Leistungseigenschaften wie up und down genießen, da Sie sozusagen "gegen den Strich" gehen.

Da Ihre Comonad Instanz definiert wurde nur Ihre zipper Funktionen, kann es nur duplicate in die Richtung, die durch Ihren Reißverschluß definiert ist, nämlich fwd und bwd (und durch Erweiterung up und down).

Bearbeiten: Nach einigem Nachdenken denke ich, dass Ihr Ansatz grundsätzlich problematisch sein wird. Ich habe meinen ursprünglichen Text beibehalten, aber es gibt ein eklatanteres Problem.

Wenn Sie versuchen, Ihre Reißverschlüsse zu überqueren, als ob sie wie jede andere 2D-Struktur wären, werden Sie Nothing mit Ihrer duplicate erhalten. Lassen Sie uns notieren, was passiert, wenn Sie tatsächlich versuchen, Ihre up, down, left, right Funktionen auf der angeblich unproblematischen duplicate (mkZipper 'a' "bc") zu verwenden.

*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 

bewegen right und left erfordert (wie Sie ordnungsgemäß mit dem Hinweis auf die unveränderliche beachten), dass jede einzelne Ihrer Unterreißverschlüsse in der Struktur homogen ist, da sonst die traverse wird aus vorzeitig ausfallen. Dies bedeutet, dass, wenn Sie tatsächlich left und right verwenden möchten, die einzige Möglichkeit, die mit duplicate nett spielt, ist, wenn Sie das einheitlichste duplicate verwenden, das möglich ist.

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

Die Alternative besteht darin, nur die Funktionen des Reißverschlusses zu verwenden. Das bedeutet, dass nur fwd und bwd und dann extract der Fokus verwendet wird und weiterhin fwd und bwd verwendet werden, um die gleiche Sache wie left und right zu erhalten. Natürlich bedeutet das, dass man auf die Fähigkeit verzichten muss, sowohl "rechts nach unten" als auch "nach unten" zu sagen, aber wie wir bereits gesehen haben, spielen Zipper nicht mit mehreren Pfaden gut.

Jetzt überprüfen wir Ihre Intuitionen, wie Sie am besten interpretieren, was mit duplicate . duplicate $ myGrid vor sich ging. Ein schönes Quadrat ist nicht wirklich die beste Art zu denken, was passiert (und Sie werden sehen, warum, wenn Sie sich auf nur extract und fwd und bwd beschränken).

*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... 

Wir haben eigentlich eine zerlumpte Struktur.

Die Quadrate innerhalb dieser zerlumpten Struktur sind auch keine Quadrate, sie werden auch zerlumpt sein. Äquivalent könnte man sich fwd als diagonal vorstellen. Oder lassen Sie Reißverschlüsse für 2-d-Strukturen ganz einfach fallen.

Meiner Erfahrung nach funktionieren Reißverschlüsse am besten, wenn sie mit baumähnlichen Dingen gepaart sind. Es würde mich nicht wundern, wenn ein Haskell-Experte eine Möglichkeit finden könnte, Reißverschlüsse und all die Aktualisierungs- und Zugriffsgüte zu verwenden, die mit solchen Dingen wie zyklischen Diagrammen oder einfach nur alten DAGs einhergeht, aber mir nicht einfällt irgendeinen von der Oberseite meines mageren Kopfes :).

So Moral der Geschichte, Reißverschlüsse sind ziemlich ein bisschen Kopfschmerzen für 2-d-Strukturen. (Unerfahrener Gedanke: Vielleicht sind Objektive interessant?)

Für die Neugierigen funktioniert meine Herangehensweise auch nur, wenn man die Zackigkeit der Struktur, mit der wir es zu tun haben, im Kopf hat; das ist fwd zweimal und dann extrahieren erhalten Sie das Äquivalent von dem, was OP in der unteren rechten Ecke seines Gitters, nicht auf der unteren linken Seite will.

Original-:

Also, was Sie brauchen, ist eine Möglichkeit, zwischen rein Reißverschluss-basierten duplicate und Ihre Traversable -basierte Duplikat zu wechseln. Der einfachste Weg ist, Ihre duplicate Funktion, die Sie bereits geschrieben haben, zu nehmen und einfach eine traverse in der Mitte hinzuzufügen.

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) 

Jetzt, da wir eine allgemeinere duplicateT können wir von irgendwelchen fiesen Code-Duplizierung von duplicate Neudefinition in Ihrem Comonad Instanz loszuwerden zu sein:

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

Dann wurde die folgende bekommt man, was man

wollen

duplicateGrid = duplicate . duplicateT 

Oder wenn Sie die Reihenfolge der Spalten und Zeilen ändern möchten, können Sie das Gegenteil tun.

Hinweis: Es wäre noch schöner, wenn Haskell können Sie nativ Typ Einschränkungen typeclasses definieren, so dass Sie verschiedene Instanzen von Comonad (alle mit newtype s vielleicht vermittelt) haben könnte für Ihre LZipper, die die Richtung Ihres duplicate ändern. Das Problem ist, dass Sie etwas wie instance Comonad LZipper (LZipper a) where ... oder das Äquivalent newtype wollen, das Sie einfach nicht in Haskell schreiben können. Du könntest vielleicht so etwas wie this mit Typfamilien machen, aber ich vermute, dass das für diese bestimmte Instanz wahrscheinlich übertrieben ist.

bearbeiten: In der Tat Sie nicht einmal duplicateT brauchen, wenn Sie die entsprechende Applicative Instanz für LZipper geben.

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) 

Jetzt nehmen Sie einfach die original duplicate Sie vor und traverse verwenden hatte.

duplicateGrid = duplicate . (traverse duplicate)