Abstrahieren über die Dimensionalität der Typen

Question

Ich baue ein Spielzeug, wo Sie Schaltungen auf einem Gitter zeichnen können und wir ihr Verhalten simulieren können. Ich dachte, es wäre ein lustiges Experiment, über die Dimensionalität des Boards zu abstrahieren und zu versuchen, den Code (typsicher) über alle Board-Dimensionen (2D, 3D, 4D usw.) hinweg arbeiten zu lassen.

Ich kann die meiste Arbeit mit GADTs und Nats machen; Angenommen, ich verwende einen Vektor als 2D-Basisabstraktion, können wir jede Dimensionalität darstellen, indem wir sie zusammensetzen;

type family Count t where 
    Count (Compose _ g) = 1 + (Count g) 
    Count _ = 0 

data Grid (n::Nat) a where 
    Grid :: f a -> Grid (Count f) a 

Das funktioniert in den meisten Fällen (leider die Art Familie erfordert UndecidableInstances)

Damit kann ich ausdrücken, dass Operationen über Gitter in Dimensionalität konsistent bleiben, dh

alter :: Grid n a -> Grid n b 

Der schwierige Bit ist, dass ich mir auch erlauben möchte, mich in den Gittern zu bewegen. Ich habe eine Representable-Instanz für Grid geschrieben, die auf dem zugrundeliegenden Representable für Compose basiert, im Grunde paaren Sie einfach die Repräsentation für jeden Funktor, der zusammengesetzt wird. In meinem Fall sind hier einige Beispiele Darstellungen:

Rep (Grid 2) ~ (Sum Int, Sum Int) 
Rep (Grid 3) ~ (Sum Int, (Sum Int, Sum Int)) 
Rep (Grid 3) ~ (Sum Int, (Sum Int, (Sum Int, Sum Int))) 

Und so weiter.

übernehmen Sie auch, dass wir Index in eine Grid durch einen Index daneben als Speicher zu halten comonad type IGrid n a = (Rep (Grid n), Grid n a)

ich einige Funktionen geschrieben haben, die sich um in einer bestimmten Dimension bewegen. Wenn eine Funktion den Fokus auf der y-Achse verschiebt, können wir diese Funktion immer noch auf jeder Dimensionalität mit mindestens 2 Dimensionen aufrufen:

z.

moveUp :: (n >= 2) => IGrid n a -> IGrid n a 

Dies ist machbar und einfach, wenn n == 2, aber für höhere Dimensionen am einfachsten ist es wahrscheinlich durch die Förderung eines niedrigeren Dimensionalität Index in eine höhere (padding unbekannt dimensional coords mit mempty) zu implementieren, so dass ich verwenden können, seek :: Rep (Grid n) -> Grid n a -> Grid n a richtig.

promote :: (m <= n) => Rep (Grid m) -> Rep (Grid n) 

Dann kann ich nur einen bestimmten Index zu jedem dim fördern, bevor es mit:

moveBy :: Rep (Grid n) -> IGrid n a -> IGrid n a 
moveBy m (rep, grid) = (rep <> m, grid) 

moveAround :: IGrid n a -> IGrid n a 
moveAround grid = grid 
       & moveBy (promote (Sum 3, Sum 2)) 
       & moveBy (promote (Sum 1)) 

Die meisten meiner Versuche, zentriert um eine typeclass verwenden und es über bestimmte Nats und mit viel Art der Umsetzung Behauptungen. Ich habe war in der Lage, einen Index um ein oder zwei endliche Ebenen zu fördern, kann aber den allgemeinen Fall nicht herausfinden.

Ich habe versucht, diese promote Funktion für einen Monat oder zwei jetzt zu schreiben, von Zeit zu Zeit zurück zu kommen und es scheint möglich, aber ich kann es einfach nicht herausfinden. Jede Hilfe würde sehr geschätzt werden. Die Verwendung von Nats und der Singletons lib ist in Ordnung, wenn das der richtige Weg ist :)

Danke, dass du dir die Zeit genommen hast, mein Dilemma zu lesen!

Answer 1

Die Größe Ihres Typenausdrucks mit einer Nat zu messen und dann zu versuchen, den Index für ein kleines Gitter in den Index für ein großes zu injizieren, ist hier zu viel. Alles, was Sie wirklich tun müssen, ist zu identifizieren, wie tief in den verschachtelten Compose Typ Sie gehen möchten, bevor Sie das Gitter ändern.

data Under g f where 
    Over :: Under f f 
    Under :: Functor h => Under g f -> Under g (Compose h f) 

Under g f wie eine natürliche Zahl geformt - vergleichen Under (Under Over) mit S (S Z) - und es sagt Ihnen, wie viele Schichten von Compose Sie von f um ablösen eine g zu finden.

under :: Under g f -> (g a -> g a) -> f a -> f a 
under Over f = f 
under (Under u) f = Compose . fmap (under u f) . getCompose 

Sie erwähnten in einem Kommentar, dass Sie mit Gittern von unendlichen Reißverschlüssen arbeiten. Es ist einfacher, Under mit verschachtelten Compose s zu verwenden, wobei das Zipper immer das linke Argument ist. Mein Grid2 ist isomorph zu Ihrem Compose Zipper Zipper.

type Zipped = Compose Zipper 
type Grid1 = Zipped Identity 
type Grid2 = Zipped Grid1 

zipped :: (Zipper (f a) -> Zipper (g b)) -> Zipped f a -> Zipped g b 
zipped f = Compose . f . getCompose 

Jetzt, da move :: Int -> Zipper a -> Zipper a, können Sie Under eine beliebige Anzahl von Compose Konstrukteurs move eine bestimmte Dimension des Rasters gehen.

moveUnder :: Under (Zipped g) f -> Int -> f a -> f a 
moveUnder u n = under u (zipped $ move n) 

Zum Beispiel up in einem 2D-Gitter zu gehen, bewegen Sie alle inneren linken Reißverschlüssen.

-- up :: Grid2 a -> Grid2 a 
up :: Functor f => Compose f (Zipped g) a -> Compose f (Zipped g) a 
up = moveUnder (Under Over) (-1) 

Nun, wenn Sie wollen auf eine Vielzahl von Dimensionen des Rasters bewegen, sobald Sie moveUnder mehrere Male nur anrufen können. Hier stelle ich eine Sequenz von Move s in eine Liste. Beachten Sie, dass ich den g in Konstruktor existenziell quantifiziere.

data Move f where 
    Move :: Under (Zipped g) f -> Int -> Move f 

movesZipped :: [Move f] -> f a -> f a 
movesZipped ms z = foldr (\(Move u n) -> moveUnder u n) z ms 

rightTwoUpOne = movesZipped [Move Over 2, Move (Under Over) (-1)]