Soru Haskell'deki Cofree CoMonad için motive edici örnekler nelerdir?


Ben oynuyordum Cofreeve oldukça grok olamaz.

Örneğin ben oynamak istiyorum Cofree [] Num Ghh içinde ve oldukça ilginç örnekler alınamıyor.

Örneğin, Cofree türü oluşturursam:

let a = 1 :< [2, 3]

Beklemek isterim extract a == 1ama bunun yerine şu hatayı alıyorum:

No instance for (Num (Cofree [] a0)) arising from a use of ‘it’
    In the first argument of ‘print’, namely ‘it’
    In a stmt of an interactive GHCi command: print it

Ve bir tür:

extract a :: (Num a, Num (Cofree [] a)) => a

Cofree'yi kullanarak, örneğin, functor'ları nasıl kullanacağınız konusunda basit örnekler verebilirim: []veya Maybeveya Either, gösterir ki

  • extract
  • extend
  • unwrap
  • duplicate?

Gönderim Tarihi: https://www.reddit.com/r/haskell/comments/4wlw70/what_are_some_motivating_examples_for_cofree/

DÜZENLEME: David Young'ın yorumunun rehberliğinde, burada ilk denemelerin yanlış yönlendirildiğini gösteren bazı daha iyi örnekler var, ancak yine de Coffon'un sezgisine rehberlik eden bazı örnekleri çok severim:

> let a = 1 :< []
> extract a
    1
> let b = 1 :< [(2 :< []), (3 :< [])]
> extract b
    1
> unwrap b
    [2 :< [],3 :< []]
> map extract $ unwrap b
    [2,3]

35
2017-08-07 17:59


Menşei


Num bir tür sınıfıdır, bir tür değil. Gibi bir şey Cofree [] Int daha uygun olurdu. Ayrıca, bu türde, kurucunun türünün de arttığını unutmayın. (:<) :: Int -> [Cofree [] Int] -> Cofree [] IntYani ikinci argüman cofree değerlerin bir listesi olmalıdır. Basit bir örnek olurdu let a = 1 :< []. Başka bir küçük örnek olurdu let a = 1 :< [x], nerede x başka mı Cofree [] Int değer. - David Young
@DavidYoung Awesome, bu benim anlayışımın büyük bir kısmına yardımcı oldu ve yazımı düzenledim. Hala coff bir sezgi seziyorum, ama şimdi görüyorum 1 :< [2, 3] 1, 2, 3'ü bir şekilde zihnimde nasıl yorumlanacağımı bilmediğim korkak bir türe zorladım. a içinde Cofree f a sadece tarafından Int, biraz korkak tip değil. Teşekkürler! - Josh.F
Cofree için sezgiyi geliştirmenin en iyi yolunun, bir grup hokkabazda denemek olduğunu düşünüyorum. Cofree Identity sonsuz bir akıştır. Cofree Belki boş olmayan bir akıştır. Cofree ((->) b), potansiyel olarak sonsuz bir Moore makinesidir (kötü bir kodlamasıdır). Cofree [], Data.Tree ürününe eşdeğer bir gül ağacıdır. - Edward KMETT
Tabii ki bunu yapamazsın. Onu daha tüketmedin bile. - JK.


Cevaplar:


Sadece tanımını tekrarlayalım Cofree veri tipi.

data Cofree f a = a :< f (Cofree f a)

Bu, sorunu örnekle teşhis etmek için yeterlidir. Yazdığın zaman

1 :< [2, 3]

Yararlı olandan çok daha alçakgönüllü bir şekilde bildirilen küçük bir hata yaptınız. İşte, f = [] ve a sayısal bir şeydir çünkü 1 :: a. Buna karşılık ihtiyacınız var

[2, 3] :: [Cofree [] a]

ve dolayısıyla

2 :: Cofree [] a

hangi could iyi ol Cofree [] a ve ayrıca Num. Tanımınız böylece tatmin edilemeyecek bir kısıtlama getiriyor ve aslında kullanım senin değerin, kısıtlamayı tatmin etme girişimi başarısız olur.

Tekrar dene

1 :< [2 :< [], 3 :< []]

ve daha iyi şansa sahip olmalısın.

Şimdi, elimizde olanı görelim. Basit tutarak başlayın. ne var Cofree f ()? Özellikle, ne Cofree [] ()? Sonuncusu fikstür için izomorf []: Her düğümün "etiketlenmemiş gül ağaçları" olarak da bilinen alt ağaçların bir listesi olduğu ağaç yapıları. Örneğin.,

() :< [  () :< [  () :< []
               ,  () :< []
               ]
      ,  () :< []
      ]

Benzer şekilde, Cofree Maybe () az ya da çok Maybe: Doğal sayıların bir kopyası, çünkü Maybe bize bir alt ağaç takmak için sıfır veya bir pozisyon verir.

zero :: Cofree Maybe ()
zero = () :< Nothing
succ :: Cofree Maybe () -> Cofree Maybe ()
succ n = () :< Just n

Önemli bir önemsiz dava Cofree (Const y) (), bir kopyasıdır y. Const y functor verir yok hayır subtrees için pozisyonlar.

pack :: y -> Cofree (Const y) ()
pack y = () :< Const y

Ardından, diğer parametreyle meşgul olalım. Her bir düğüme ne tür bir etiket eklediğinizi bildirir. Parametreleri daha anlamlı bir şekilde yeniden adlandırma

data Cofree nodeOf label = label :< nodeOf (Cofree nodeOf label)

Etiketlediğimizde (Const y) örnek olsun çiftleri

pair :: x -> y -> Cofree (Const y) x
pair x y = x :< Const y

Rakamlarımızın düğümlerine etiket eklediğimizde, boş değil listeleri

one :: x -> Cofree Maybe x
one = x :< Nothing
cons :: x -> Cofree Maybe x -> Cofree Maybe x
cons x xs = x :< Just xs

Ve listeler için etiketli gül ağaçları.

0 :< [  1 :< [  3 :< []
             ,  4 :< []
             ]
     ,  2 :< []
     ]

Bu yapılar her zaman "muaf değildir", çünkü hiçbir çocuğu olmasa bile en azından bir üst düğüm vardır ve bu düğümün her zaman bir etiketi olacaktır. extract işlem, üst düğümün etiketini verir.

extract :: Cofree f a -> a
extract (a :< _) = a

Yani, extract atar bağlam Üst etiketin

Şimdi duplicate operasyon süsleyen her etiketle Kendi bağlamı.

duplicate :: Cofree f a -> Cofree f (Cofree f a)
duplicate a :< fca = (a :< fca) :< fmap duplicate fca  -- f's fmap

Alabiliriz Functoriçin örnek Cofree f bütün ağacı ziyaret ederek

fmap :: (a -> b) -> Cofree f a -> Cofree f b
fmap g (a :< fca) = g a :< fmap (fmap g) fca
    --                     ^^^^  ^^^^
    --                 f's fmap  ||||
    --                           (Cofree f)'s fmap, used recursively

Bunu görmek zor değil

fmap extract . duplicate = id

Çünkü duplicate her düğümün içeriği ile süslenir, sonra fmap extract dekorasyonu atar.

Bunu not et fmap Çıktının etiketlerini hesaplamak için sadece girdinin etiketlerine bakar. Her giriş etiketine bağlı olarak çıktı etiketlerini hesaplamak istediğimizi varsayalım bağlamında? Örneğin, işaretlenmemiş bir ağaç verildiğinde, her düğümü tüm alt ağacının boyutuyla etiketlemek isteyebiliriz. Teşekkürler Foldableiçin örnek Cofree f, düğümleri saymalıyız.

length :: Foldable f => Cofree f a -> Int

Yani bu demektir ki

fmap length . duplicate :: Cofree f a -> Cofree f Int

Comonad'ların temel fikri, "bazı içerikli şeyleri" yakalamaları ve içeriğe bağlı haritaları her yerde uygulamanıza izin vermeleridir.

extend :: Comonad c => (c a -> b) -> c a -> c b
extend f = fmap f       -- context-dependent map everywhere
           .            -- after
           duplicate    -- decorating everything with its context

tanımlanması extend daha doğrudan, çoğaltma zahmetinden kurtarır (ancak bu sadece paylaşım miktarlarıdır).

extend :: (Cofree f a -> b) -> Cofree f a -> Cofree f b
extend g ca@(_ :< fca) = g ca :< fmap (extend g) fca

Ve sen alabilirsiniz duplicate geri alarak

duplicate = extend id -- the output label is the input label in its context

Dahası, eğer sen seçersen extract İçeride her bir etikete yapılacak şey olarak, her etiketi arkasından geldiği yere yerleştirirsiniz:

extend extract = id

Bu "bağlamdaki etiketler üzerindeki işlemler", "ortak Kleisli okları" olarak adlandırılır.

g :: c a -> b

ve işi extend bir Kleisli okunu bütün yapılar üzerinde bir işlev olarak yorumlamaktır. extract işlem co-Kleisli okudur ve tarafından yorumlanır. extend kimlik işlevi olarak. Tabii ki, bir Kleisli bileşimi var

(=<=) :: Comonad c => (c s -> t) -> (c r -> s) -> (c r -> t)
(g =<= h) = g . extend h

ve comonad yasaları bunu sağlamak =<= birleştirici ve emer extractBize Kleisli kategorisini veriyor. Dahası var

extend (g =<= h)  =  extend g . extend h

Böylece extend bir funktoru (kategorik anlamda) co-Kleisli kategorisinden set-ve-işlevlerine kadar. Bu yasaların kontrol edilmesi zor değildir Cofree, takip ettikleri gibi Functor düğüm şekli için yasalar.

Şimdi, bir coff comonad'da bir yapıyı görmenin kullanışlı bir yolu, bir çeşit "oyun sunucusu" dır. Yapı

a :< fca

Oyunun durumunu temsil eder. Oyunda bir hareket "durdurma" dan oluşur, bu durumda aya da "devam etmek", fca. Örneğin düşünün

Cofree ((->) move) prize

Bu sunucu için bir istemci ya durmalı ya da move: bu bir liste arasında moves. Oyun şu şekilde oynanır:

play :: [move] -> Cofree ((->) move) prize -> prize
play []       (prize :< _) = prize
play (m : ms) (_     :< f) = play ms (f m)

Belki bir move bir Char ve prize karakter dizisini ayrıştırmanın sonucudur.

Yeterince sert bakarsanız, göreceksiniz ki [move] bir sürümüdür Free ((,) move) (). Serbest monadlar müşteri stratejilerini temsil eder. Functor ((,) move) sadece komutla bir komut arabiriminde tutar "gönder move". ((->) move) karşılık gelen yapıdır " move".

Bazı functor'lar bir komut arabirimini yakalamak olarak görülebilir; Böyle bir eğlence için serbest monad, komutları yapan programları temsil eder; Functor, komutlara nasıl yanıt verileceğini temsil eden bir "ikili" ye sahip olacak; ikilinin cofree comonad'ı, komutları yapan programların çalıştırılabileceği genel bir kavramdır. Program, program durup bir değer döndürürse ne yapılacağını söyler ve eğer programın çalıştırılmasında nasıl devam edeceğini söyleyen alt yapılardır. bir komut verir.

Örneğin,

data Comms x = Send Char x | Receive (Char -> x)

karakterlerin gönderilmesine veya alınmasına izin verilmesini tanımlar. Onun çift

data Responder x = Resp {ifSend :: Char -> x, ifReceive :: (Char, x)}

Bir egzersiz olarak, etkileşimi uygulayıp uygulayamayacağınızı görün

chatter :: Free Comms x -> Cofree Responder y -> (x, y)

53
2017-08-07 19:41



Madde ve antimaddenin yok edilmesi hakkında daha fazlası Kmett'in blogunda - Benjamin Hodgson♦
@pigworker Free-cofree "iptal" çalışması için, funktörlerin yaşandığı kategoriden bazı özel özellikler gerektiriyor mu? - danidiaz
harika çünkü data Cofree nodeOf label = label :< nodeOf (Cofree nodeOf label)ko-kleisli oklarla bağları açıklamak ve oyunun motive edici örneğinin yanı sıra katlanılabilir (artı sonunda yararlı bir egzersiz). Teşekkürler! - Josh.F
@danidiaz Bir şeye itiraz ediyor gibisiniz. Sadece ne demek istediğini söyle. Aklımda Haskell, kümeler ve işlevler kategorisinde saf toplam programlar yürütmek için bana (çok fazla ama en azından) yeterli anlambilim sunuyor. Bu ortamda, indüktif tiplerin (serbest monadlar gibi: müşterinin bir sona erme misyonu gibi), kondüktif tiplerden (cofree comonad'lar gibi) ayrılması önemlidir: sunucu, müşterinin istediği kadar uzağa yapışmalıdır. Ön işlemcim yazmamı sağlıyor codata bir anahtar kelime olarak, belgeler için. - pigworker
@pigworker Bunu bir Dokümantasyona dönüştürmekle mi akıl edersiniz? - wheaties