SORU
18 EKİM 2012, PERŞEMBE


Yazılı ya da n-boyutlu ızgara türü için cojoin cobind

Tür düzeyinde doğal, normal tanımı kullanarak, n-boyutlu bir ızgara tanımlanan ettim.

{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE TypeFamilies #-}

data Nat = Z | S Nat

data U (n :: Nat) x where
  Point :: x -> U Z x
  Dimension :: [U n x] -> U n x -> [U n x] -> U (S n) x

dmap :: (U n x -> U m r) -> U (S n) x -> U (S m) r
dmap f (Dimension ls mid rs) = Dimension (map f ls) (f mid) (map f rs)

instance Functor (U n) where
  fmap f (Point x) = Point (f x)
  fmap f d@Dimension{} = dmap (fmap f) d

Şimdi Comonad bir örnek yapmak istiyorum, ama oldukça kafamı toplamam edemem.

class Functor w => Comonad w where
  (=>>)    :: w a -> (w a -> b) -> w b
  coreturn :: w a -> a
  cojoin   :: w a -> w (w a)

  x =>> f = fmap f (cojoin x)
  cojoin xx = xx =>> id

instance Comonad (U n) where
  coreturn (Point x) = x
  coreturn (Dimension _ mid _) = coreturn mid

  -- cojoin :: U Z x -> U Z (U Z x)
  cojoin (Point x) = Point (Point x)
  -- cojoin ::U (S n) x -> U (S n) (U (S n) x)
  cojoin d@Dimension{} = undefined

  -- =>> :: U Z x -> (U Z x -> r) -> U Z r
  p@Point{} =>> f = Point (f p)
  -- =>> :: U (S n) x -> (U (S n) x -> r) -> U (S n) r
  d@Dimension{} =>> f = undefined

N-boyutlu bir ızgara üzerinde cojoin kullanarak, n-boyutlu kılavuzlar n-boyutlu bir ızgara oluşturur. Örneği sağladıklarını olan this one, aynı fikir istiyorumdeğercojoinedkılavuz (x,y,z) olmalıdırözgünkılavuzduruldu(x,y,z). Bu kodu uyarlamak, n yapmak için n reify ihtiyacımız var gibi görünüyor "" ve n "rulo". fmaps Bunu bu şekilde yapmak zorunda değilsin ama eğer yardımcı olacaksa, o zaman işte.

CEVAP
27 EKİM 2012, CUMARTESİ


Her zaman istediğini elde edemezsin, ama eğer denerseniz bazen sadece ihtiyacın olanı alıyorsun. Jagger/Richards:

Listelerde imleçler

Bana yapısındaki bileşenler snoc - ve eksilerini listeler uzamsal özelliklerini açık tutmak için kullanarak yeniden inşa edelim. Ben tanımlayın

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)

Hadi comonads

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

ve Haydi imleçler comonads emin olun

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

Eğer bu tür şeyler için açık iseniz, Cursor InContext [] mekansal hoş bir türevi olduğunu unutmayın

InContext f x = (x, ∂f x)

tahsis bir functor resmi türev alır, bir delikten kendi düşüncesini içerik sağlar. InContext f her zaman Comonad bahsedildiği gibi this answer, ve ne biz burada sadece Comonad indüklenmiş diferansiyel yapısı, nerede counit özler elemanı odağı ve cojoin süsleyen her öğe ile kendi bağlamında, etkili bir şekilde veren bir bağlam tam odaklandık imleçler ve imleç ile bir kadın hiç de odak noktası. Bir örnek yapalım.

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

Gördün mü? 2 odağı oldu süslü olmak için imleç-at-2; için sol, biz listenin imleç-at-1; hakkı, listenin imleç-at-3 ve imleç-at-4.

Beste İmleçler, İmleçler Aktaran?

Şimdi, Comonad olmak istiyorsun yapısı Cursor n kat kompozisyonu. Verin bakalım

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

Comonads f g beste yapmaya ikna etmek, counits düzgünce oluştur, ama ihtiyacınız olan bir "dağılma Kanunu"

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

kompozit cojoin böyle yapabilirsiniz

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

Kanunlar transpose tatmin ne yapmalıyım? Muhtemelen gibi bir şey

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

ya f ve g bazı sıra shoogle için her iki yoldan başka bir sipariş emin olmak için ne gerekiyorsa aynı sonucu verir.

Kendisi ile Cursor transpose bir tanımlayabilir miyiz? Hukuka çeşit bir yolu da ucuza Bwd 57 *olduğunu unutmayınzippilyuygulamalı, dolayısıyla çok 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)

Ve burada koklamak için fare başlamalıdır. Uyuşmazlığı sonuçları şekilkesilmekendi sırasını kendi kendine ters olduğunu açıkça arzu özelliğini kırmak için gidiyor , ve. Raggedness her türlü hayatta olmaz. Hukuka operatörü alırım: sequenceA ve tamamen normal veriler için, tüm parlak ve güzel.

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

Ama ben sadece uyum, iç imleçler bir hareket bile (hiç boyutlarda düzensiz hale zihin), bu dönemi atlatmak.

> 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

Bir dış imleç konumu ve birden fazla iç imleç pozisyonlar varsa, iyi davranacak olan hukuka yok. Kendi kendine beste Cursor iç yapıları düzensiz bir diğerine göre sağlar, 64**, no cojoin hayır. Ve yaptım, tanımlayabilirsiniz

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

ama bizi biz iç yapıları düzenli tutmak emin olmak için bir sorumluluk. Eğer bu yükü kabul etmeye istekli iseniz, o zaman Applicative Traversable kolayca kompozisyon altında kapalı olduğundan yineleme yapabilirsiniz. Burada bit ve parçaları

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

Düzenleme:bütünlüğü için, burada normal, ne zaman yaptığı şey bu

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

Hancock'un Tensör Ürün

Düzenlilik için, bir kompozisyon daha güçlü gerekir. Kavramını yakalamak gerekir "f-Yapı g-yapıları---aynı şekil bir". Bu ne paha biçilmez Peter Hancock aramalar "tensör ürün" hangi yazarım f :><: g: orada bir "dış" f-şekli ve bir "iç" g-şekil ortak olan tüm iç g-yapıları, yani hukuka kolayca tanımlanabilir ve her zaman kendine ters. Hancock'un tensör Haskell yer alan tanımlı değil, ama bir bağımlı olarak yazılan ayarı, kolay "kapsayıcı" olan bu tensör var. bir fikri formüle etmek.

Size bir fikir vermek için, bir kabın kavramı dejenere düşünün

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

s türü diyoruz "" ve p "yazın. pozisyonları şekilleri Bir değeri bir şekil seçimi ve her pozisyonda x bir depolama oluşmaktadır. Bağımlı durumda, bu tür pozisyonlar olabilir bağlı seçim şekli (örneğin, liste, şekil numarası (uzunluğu), ve birçok pozisyon). Bu kaplar tensör bir ürün var

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

hangi genel bir matris gibidir: boyutları ve pozisyonları her çifte bir öğe var şekil bir çift. Sen-ebilmek yapmak bu çok iyi zaman türleri p p' bağlı değerler s s' ve tam olarak Hancock tanımı tensör ürün kaplar.

Tensör Ürünler için içerik

p-1 lise, ∂(s :<| p) = (s, p) :<| (p-1) içinde öğrenmiş olabilir gibi şimdi, p daha az eleman ile türü. Gibi tahsis(s*x^p) = (s*s)*x^(p-1). Size bir konum (şeklinde kayıt) seçin ve silin. Budak p-1 ellerinizi türleri bağımlı olmadan almak zor olmasıdır. Ama InContext bir pozisyon seçersilmeden.

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

Bu da bağımlı dava için çalışır, ve biz sevinçle kazanırlar

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

Şimdi InContext f her zaman Comonad ve bu InContexts tensör çarpımları kendilerini olduklarından comonadic bize bu bir olduğunu biliyoruz InContextler. Bu pozisyonu her boyut ve her şeyi size tam olarak bir pozisyon verir) sen seç, bir dış pozisyonu ve iç çok pozisyona vardı daha önce, diyelim. Tensör ürün bileşimi yerine, her şeyi tatlı bir şekilde çalışır.

Naperian Funktorlar

Ancak tensör ürün ve kompozisyonu denk Functor bir alt sınıfı vardır. Bunlar f () ~ ()Functor s f: yani, zaten tek bir şekli var, kompozisyonları pejmürde değerleri en başta eledik. Functors Bu 97 ** bazı pozisyon düşünebiliriz p olarak ayarlamak için dönmesidirlogaritma(x f x vermek için yükseltilmiş olması gerekir üs). Buna karşılık, Hancock John Napier sonra Naperian bu funktorlar aramalar Hancock yaşadığı yer Edinburgh parçası musallat olan.

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

Naperian bir functor bir logaritma, projectiyon fonksiyonu elemanları orada bulunan pozisyonlar eşleme ikna etti. Naperian funktorlar zippily pure 108 *ilgili* 106 *K ve tahminler için combinators. Ayrıca mümkün olan her pozisyonda çok pozisyon temsili depolandığı bir değer oluşturmak için. Memnun bir şekilde açılır hatırlarsınız olan logaritma kanunları.

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)

Sabit boyutlu dizi olduğunu unutmayın (birvektör) Void olan One sabit birim eşleme nerede (Id :*: Id :*: ... :*: Id :*: One) tarafından verilir. Bir dizi bu kadar Naperian. Şimdi, biz de var

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

çok boyutlu diziler Naperian anlamına gelir.

Naperian f InContext f bir sürümünü oluşturmak için bir pozisyon için nokta!

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

Yani, özellikle, Focused n-boyutlu bir dizi gerçekten bir comonad olacak. Vektörler bir kompozisyon vektörler Naperian çünkü n vektör tensör bir ürün. Ama Focused n boyutlu bir dizi n kat tensör ürün olacakkompozisyon değilbu n Focused boyutları belirleyen vektörler. Fermuar açısından bu comonad ifade etmek mümkün tensör ürün oluşturmak için yapar bir form bunları ifade etmek lazım. Gelecek için bir egzersiz olarak bırakıyorum.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Dirty Loops

    Dirty Loops

    21 Mayıs 2007
  • ElChakotay Andrich

    ElChakotay A

    10 EKİM 2013
  • Jonnyriddlin1

    Jonnyriddlin

    4 Ocak 2007