Pisanie cojoin lub cobind dla typu siatki n-wymiarowej

Jagger / Richards: nie zawsze możesz dostać to, czego chcesz, ale jeśli kiedyś spróbujesz, może się okazać, że dostaniesz to, czego potrzebujesz.

Kursory na listach

Pozwól mi przebudować komponenty Twojej struktury za pomocą snoc-i cons-list, aby zachować właściwości przestrzenne jasne. Definiuję

data Bwd x = B0 | Bwd x :< x deriving (Functor, Foldable, Traversable, Show)
data Fwd x = F0 | x :> Fwd x deriving (Functor, Foldable, Traversable, Show)
infixl 5 :<
infixr 5 :>

data Cursor x = Cur (Bwd x) x (Fwd x) deriving (Functor, Foldable, Traversable, Show)

Let ' s have comonads

class Functor f => Comonad f where
  counit  :: f x -> x
  cojoin  :: f x -> f (f x)

I upewnijmy się, że kursory są komonadami

instance Comonad Cursor where
  counit (Cur _ x _) = x
  cojoin c = Cur (lefts c) c (rights c) where
    lefts (Cur B0 _ _) = B0
    lefts (Cur (xz :< x) y ys) = lefts c :< c where c = Cur xz x (y :> ys)
    rights (Cur _ _ F0) = F0
    rights (Cur xz x (y :> ys)) = c :> rights c where c = Cur (xz :< x) y ys

Jeśli jesteś włączony do tego rodzaju rzeczy, można zauważyć, że Cursor jest przestrzennie przyjemnym wariantem InContext []

InContext f x = (x, ∂f x)

Gdzie ∂ przyjmuje formalną pochodną funktora, dając jego pojęcie kontekstu jednowierszowego. InContext f jest zawsze Comonad, Jak wspomniano w ta odpowiedź , a to, co mamy tutaj, to po prostu Comonad indukowane przez strukturę różniczkową, gdzie {28]} wydobywa element w centrum uwagi i {29]} dekoruje każdy element swoim własnym kontekstem, skutecznie dając kontekst pełen zmienionych kursorów i z niewzruszonym kursorem na jego miejscu. skup się. Weźmy przykład.

> cojoin (Cur (B0 :< 1) 2 (3 :> 4 :> F0))
Cur (B0 :< Cur B0 1 (2 :> 3 :> 4 :> F0))
    (Cur (B0 :< 1) 2 (3 :> 4 :> F0))
    (  Cur (B0 :< 1 :< 2) 3 (4 :> F0)
    :> Cur (B0 :< 1 :< 2 :< 3) 4 F0
    :> F0)

Struktura, o którą prosisz, to n-składowa Cursor. Let ' s have

newtype (:.:) f g x = C {unC :: f (g x)} deriving Show

Aby przekonać komonady f i g do komponowania, counit s komponują starannie, ale ty potrzeba "prawa dystrybucyjnego"

transpose :: f (g x) -> g (f x)

Więc możesz zrobić kompozyt cojoin w ten sposób

f (g x)
  -(fmap cojoin)->
f (g (g x))
  -cojoin->
f (f (g (g x)))
  -(fmap transpose)->
f (g (f (g x)))

counit . transpose = fmap counit
cojoin . transpose = fmap transpose . transpose . fmap cojoin

Lub cokolwiek innego, aby upewnić się, że dowolne dwa sposoby shootgle pewnej sekwencji f I g z jednego rozkazu do drugiego dają ten sam wynik.

Czy możemy zdefiniować transpose dla Cursor z samym sobą? Jednym ze sposobów na tanią transpozycję jest zwrócenie uwagi, że Bwd i Fwd są zippily aplikacyjny, stąd tak jest Cursor.

instance Applicative Bwd where
  pure x = pure x :< x
  (fz :< f) <*> (sz :< s) = (fz <*> sz) :< f s
  _ <*> _ = B0

instance Applicative Fwd where
  pure x = x :> pure x
  (f :> fs) <*> (s :> ss) = f s :> (fs <*> ss)
  _ <*> _ = F0

instance Applicative Cursor where
  pure x = Cur (pure x) x (pure x)
  Cur fz f fs <*> Cur sz s ss = Cur (fz <*> sz) (f s) (fs <*> ss)

I tutaj powinieneś zacząć wąchać szczura. Niedopasowanie kształtu powoduje obcięcie , A to złamie oczywiście pożądaną właściwość, że SELF-transpose jest SELF-inverse. Każdy rodzaj szarpaniny nie przetrwa. Otrzymujemy operator transpozycyjny: sequenceA, A Dla całkowicie regularnych danych, wszystko jest jasne i piękne.

> regularMatrixCursor
Cur (B0 :< Cur (B0 :< 1) 2 (3 :> F0))
          (Cur (B0 :< 4) 5 (6 :> F0))
          (Cur (B0 :< 7) 8 (9 :> F0) :> F0)
> sequenceA regularMatrixCursor
Cur (B0 :< Cur (B0 :< 1) 4 (7 :> F0))
          (Cur (B0 :< 2) 5 (8 :> F0))
          (Cur (B0 :< 3) 6 (9 :> F0) :> F0)

Ale nawet jeśli po prostu przesunę jeden z wewnętrznych kursorów poza wyrównanie (nieważne co rozmiary poszarpane), wszystko idzie nie tak.

> raggedyMatrixCursor
Cur (B0 :< Cur ((B0 :< 1) :< 2) 3 F0)
          (Cur (B0 :< 4) 5 (6 :> F0))
          (Cur (B0 :< 7) 8 (9 :> F0) :> F0)
> sequenceA raggedyMatrixCursor
Cur (B0 :< Cur (B0 :< 2) 4 (7 :> F0))
          (Cur (B0 :< 3) 5 (8 :> F0))
          F0

Gdy masz jedną zewnętrzną pozycję kursora i wiele wewnętrznych pozycji kursora, nie ma transpozycji, która zachowałaby się dobrze. Samo-komponowanie Cursor pozwala na postrzępienie wewnętrznych struktur względem siebie, więc nie transpose, Nie cojoin. Możesz, a ja zdefiniowałem

instance (Comonad f, Traversable f, Comonad g, Applicative g) =>
  Comonad (f :.: g) where
    counit = counit . counit . unC
    cojoin = C . fmap (fmap C . sequenceA) . cojoin . fmap cojoin . unC

instance (Functor f, Functor g) => Functor (f :.: g) where
  fmap h (C fgx) = C (fmap (fmap h) fgx)

instance (Applicative f, Applicative g) => Applicative (f :.: g) where
  pure = C . pure . pure
  C f <*> C s = C (pure (<*>) <*> f <*> s)

instance (Functor f, Foldable f, Foldable g) => Foldable (f :.: g) where
  fold = fold . fmap fold . unC

instance (Traversable f, Traversable g) => Traversable (f :.: g) where
  traverse h (C fgx) = C <$> traverse (traverse h) fgx

Edit: dla kompletności, oto co robi, gdy wszystko jest regularne,

> cojoin (C regularMatrixCursor)
C {unC = Cur (B0 :< Cur (B0 :<
  C {unC = Cur B0 (Cur B0 1 (2 :> (3 :> F0))) (Cur B0 4 (5 :> (6 :> F0)) :> (Cur B0 7 (8 :> (9 :> F0)) :> F0))}) 
 (C {unC = Cur B0 (Cur (B0 :< 1) 2 (3 :> F0)) (Cur (B0 :< 4) 5 (6 :> F0) :> (Cur (B0 :< 7) 8 (9 :> F0) :> F0))})
 (C {unC = Cur B0 (Cur ((B0 :< 1) :< 2) 3 F0) (Cur ((B0 :< 4) :< 5) 6 F0 :> (Cur ((B0 :< 7) :< 8) 9 F0 :> F0))} :> F0))
(Cur (B0 :<
  C {unC = Cur (B0 :< Cur B0 1 (2 :> (3 :> F0))) (Cur B0 4 (5 :> (6 :> F0))) (Cur B0 7 (8 :> (9 :> F0)) :> F0)})
 (C {unC = Cur (B0 :< Cur (B0 :< 1) 2 (3 :> F0)) (Cur (B0 :< 4) 5 (6 :> F0)) (Cur (B0 :< 7) 8 (9 :> F0) :> F0)}) 
 (C {unC = Cur (B0 :< Cur ((B0 :< 1) :< 2) 3 F0) (Cur ((B0 :< 4) :< 5) 6 F0) (Cur ((B0 :< 7) :< 8) 9 F0 :> F0)} :> F0))
(Cur (B0 :<
  C {unC = Cur ((B0 :< Cur B0 1 (2 :> (3 :> F0))) :< Cur B0 4 (5 :> (6 :> F0))) (Cur B0 7 (8 :> (9 :> F0))) F0})
 (C {unC = Cur ((B0 :< Cur (B0 :< 1) 2 (3 :> F0)) :< Cur (B0 :< 4) 5 (6 :> F0)) (Cur (B0 :< 7) 8 (9 :> F0)) F0})
 (C {unC = Cur ((B0 :< Cur ((B0 :< 1) :< 2) 3 F0) :< Cur ((B0 :< 4) :< 5) 6 F0) (Cur ((B0 :< 7) :< 8) 9 F0) F0} :> F0)
:> F0)}

Iloczyn tensorowy Hancocka

Dla regularności, potrzebujesz czegoś mocniejszego niż kompozycja. Musisz być w stanie uchwycić pojęcie "f-struktura g-struktury-wszystko-ten-sam-kształt". To jest to, co nieocenionym Peter Hancock nazywa "iloczyn tensorowy" , który napiszę f :><: g: istnieje jeden "zewnętrzny" kształt f i jeden "wewnętrzny" kształt g wspólny dla wszystkich wewnętrznych struktur g, więc transpozycja jest łatwo definiowalna i zawsze odwrotna do siebie. Tensor Hancocka nie jest wygodnie definiowalny w Haskell, ale w zależności od typowania łatwo jest sformułować pojęcie "kontenera", który ma ten tensor.

Aby dać ci pomysł, rozważ zdegenerowane pojęcie kontenera

data (:<|) s p x = s :<| (p -> x)

Gdzie mówimy s jest typem "kształtów" i p typem "pozycji". A wartość składa się z wyboru kształtu i przechowywania x w każdej pozycji. W zależności od przypadku, rodzaj pozycji może zależeć od wyboru kształtu (np. dla list, kształt jest liczbą (długość), i masz tyle pozycji). Pojemniki te mają iloczyn tensorowy

(s :<| p) :><: (s' :<| p')  =  (s, s') :<| (p, p')

Która jest jak macierz uogólniona: para kształtów daje wymiary, a następnie masz element w każdej parze pozycji. Możesz to zrobić doskonale, gdy typy p i p' zależą od wartości w s i s' i to jest dokładnie definicja iloczynu tensorowego kontenerów.

InContext dla iloczynów Tensorowych

Teraz, jak być może nauczyłeś się w liceum, ∂(s :<| p) = (s, p) :<| (p-1) gdzie p-1 jest typem z jednym pierwiastkiem mniej niż p. Jak ∂(S x^p) = (sp) * x^(p-1). Zaznaczasz jedną pozycję (zapisujesz ją w kształcie) i usuwasz. Problem polega na tym, że p-1 jest trudny do zdobycia bez zależnych typów. Ale InContext wybiera pozycję bez jej usuwania .

InContext (s :<| p) ~= (s, p) :<| p

InContext (f :><: g) ~= InContext f :><: InContext g

Teraz wiemy, że InContext f jest zawsze Comonad, a to nam mówi, że iloczyn tensorowy InContext s są komonadyczne, ponieważ same są {60]}s. to znaczy, wybieramy jedną pozycję na wymiar (a to daje dokładnie jedną pozycję w całej rzeczy), gdzie wcześniej mieliśmy jedną pozycję zewnętrzną i wiele pozycji wewnętrznych. Z produkt tensor zastępujący kompozycję, wszystko działa słodko.

Naperian Functors

Ale istnieje podklasa Functor, dla której iloczyn tensorowy i skład są zbieżne. Są to Functor s f, dla których f () ~ (): tzn. i tak jest tylko jeden kształt, więc w kompozycjach nie ma wartości. Te Functor S są izomorficzne do (p ->) dla pewnego zbioru pozycji p, który możemy traktować jako logarytm (wykładnik do którego należy podnieść x, aby dać f x). Hancock nazywa tych [74] funktorami po Johnie Napierze (którego duch nawiedza część Edynburga, w której mieszka Hancock).

class Applicative f => Naperian f where
  type Log f
  project :: f x -> Log f -> x
  positions :: f (Log f)
  --- project positions = id

A Naperian funktor ma logarytm, indukujący projectfunkcję jonową odwzorowującą pozycje na Znalezione tam pierwiastki. Naperian funktory są wszystkie zippily Applicative, Z pure i <*> odpowiadającymi kombinatorom K I S dla projekcji. Możliwe jest również skonstruowanie wartości, gdzie przy każdym pozycja jest przechowywana, że właśnie reprezentacji pozycji. Prawa logarytmów, które możesz zapamiętać, pojawiają się przyjemnie.

newtype Id x = Id {unId :: x} deriving Show

instance Naperian Id where
  type Log Id = ()
  project (Id x) () = x
  positions = Id ()

newtype (:*:) f g x = Pr (f x, g x) deriving Show

instance (Naperian f, Naperian g) => Naperian (f :*: g) where
  type Log (f :*: g) = Either (Log f) (Log g)
  project (Pr (fx, gx)) (Left p) = project fx p
  project (Pr (fx, gx)) (Right p) = project gx p
  positions = Pr (fmap Left positions, fmap Right positions)

Zauważ, że tablica o stałej wielkości (awektor ) jest dana przez (Id :*: Id :*: ... :*: Id :*: One), gdzie One jest funkcją jednostki stałej, której logarytm wynosi Void. Więc tablica to Naperian. Teraz mamy również

instance (Naperian f, Naperian g) => Naperian (f :.: g) where
  type Log (f :.: g) = (Log f, Log g)
  project (C fgx) (p, q) = project (project fgx p) q
  positions = C $ fmap (\ p -> fmap (p ,) positions) positions

Co oznacza, że tablice wielowymiarowe są Naperian.

Aby skonstruować wersję InContext f dla Naperian f, wystarczy wskazać pozycji.

data Focused f x = f x :@ Log f

instance Functor f => Functor (Focused f) where
  fmap h (fx :@ p) = fmap h fx :@ p

instance Naperian f => Comonad (Focused f) where
  counit (fx :@ p) = project fx p
  cojoin (fx :@ p) = fmap (fx :@) positions :@ p

Więc, w szczególności, Focused N-wymiarowa tablica będzie rzeczywiście komonad. Zbiór wektorów jest iloczynem tensorowym n wektorów, ponieważ wektory są Naperian. Ale Focused N-wymiarowa tablica będzie N-krotnym iloczynem tensorowym, nie składem N Focused wektorów, które wyznaczają jego wymiary. Aby wyrazić to comonad w kategoriach iloczynu tensorowego, musimy wyrazić je w postaci umożliwiającej skonstruowanie iloczynu tensorowego. Ja zostaw to jako ćwiczenie na przyszłość.