Last serbest bir monoid midir?

Question

Serbest monoidler genellikle "liste monoidleri" olarak kabul edilir. Yine de, bize serbest monoidler verebilecek diğer olası yapılarla ilgileniyorum .

İlk olarak, serbest monoidlerin tanımının üzerinden geçelim . Serbest bir monoidi, monoid kanunlara ve başka hiçbir şeye uymayan bir yapı olarak tanımlamanın nasıl mümkün olduğunu hiçbir zaman tam olarak anlamadım . Bir şeyin yukarıda belirtilenler dışında hiçbir kurala uymadığını nasıl kanıtlarız? Yoksa bu sadece bir sezgi mi?

Her neyse, functors konuşacağız. Bazı monoidler özgürse, ücretsiz bir functor ile elde ederiz . Burada bir listenin oldukça kullanışlı olduğu açıktır:

free :: Set -> Mon
free a = ([a], (++), [])

Yine de, birkaç tane daha ortaya çıkabilir. Örneğin, aşağıda için biridir Lastait Data.Monoid:

freeLast :: Set -> Mon
freeLast a = (Last a, (<>) :: Last a -> Last a -> Last a, Last Nothing) 

Yani, bu funktor yapar Lastbir serbest Monoid ? Varsa Daha genel olarak yasalara saygılı için örneği Monoid (T a)olduğunu Tbir serbest monoid ?

Answer 1

Serbest bir monoidi anlamanın bir yolu şudur: Biri size bir değer verirse, nasıl yaratıldığına dair ne kadar çıkarım yapabilirsiniz? Doğal sayılardan oluşan toplamsal bir monoid düşünün. Sana 7 veriyorum ve nasıl aldığımı soruyorum. 4 + 3 veya 3 + 4 veya 2 + 5 vb. Ekleyebilirdim. Pek çok olasılık var. Bu bilgi kayboldu. Öte yandan, size bir liste verirsem [4, 3], tekillerden [4]ve [3]. []İşin içinde bir birim olması dışında . Belki [4]<>[3]<>[]ya da [4]<>[]<>[]<>[3]. Ama kesinlikle değildi [3]<>[4].

Daha uzun bir listeyle, [1, 2, 3]ek seçeneklere ([1]<>[2]) <> [3]veya [1] <> ([2]<>[3])boş listenin tüm olası eklerine sahip olursunuz . Dolayısıyla, kaybettiğiniz bilgiler birim yasalarını ve çağrışımları izler, ancak başka hiçbir şey yoktur . Serbest bir monoid değer, nasıl yaratıldığını, modulo birim yasalarını ve birlikteliği hatırlar.

Answer 2

Örnek olarak, negatif olmayan Tamsayı sayıları, yani 0,1,2,.... Kaç tane monoid yapabiliriz?

Tanımlanması mempty = 0ve (<>) = (+). Bunun bir monoid olduğunu kolayca kanıtlayabilirsiniz.

Tanımlanması mempty = 1ve (<>) = (*). Yine, bu bir monoid (Kanıtla, kolay)

Yukarıda tanımlanan iki monoid, Doğal sayılar yerine toplamsal ve çarpımsal monoidler olarak adlandırılır . Yapı olarak farklıdırlar, örneğin, 0çarpımsal monoiddeki öğe, toplamsal monoiddeki diğer öğelerden tamamen farklı davranır, dolayısıyla Doğal sayılara içsel bir şey vardır, bu da bu monoidleri farklı kılar (bu iddiayı bir sonraki paragrafa kadar tutun ).

Yaratabileceğimiz üçüncü bir monoid var, hadi buna birleştirme monoid diyelim .

Tanımlanması mempty = no-actionve (<>) = glue one integer beside the other.

Örnek olarak 3 <> mempty = 3ve 3 <> 2 = 32. Unsurların doğal sayılar olduğu gerçeğinin burada önemli olmadığına dikkat edin. Doğal yerine Rasyonelleri ya da hangi sembolleri severseniz seçin, monoid tam olarak aynı şey olacaktır. (* Dipnotu okuyun) Dolayısıyla, monoidin diğerlerinden farklı olmasını sağlayan altta yatan kümede hiçbir şey yoktur . Bu nedenle, monoid ücretsizdir çünkü Naturals'ın aritmetik kurallarına veya monoid olanlardan başka herhangi bir kurala bağlı değildir.

Ve bu, temeldeki kümenin iç kurallarına bağlı olarak değil, özgürce bir monoidi oluşturmanın tek yoludur. Elbette, birleştirme haskell'de listeler olarak ifade edilir.

• Not: Tek önemli nokta, aynı sayıda öğeyi paylaşmalarıdır. Örneğin, serbest 3 elemanları ile monoid a, bve cbu üç herhangi keyfi birleştirme olurdu, ama hiç neler sembol seçebilirsiniz: 1, 2, 3veya α, β, γ... ve monoid aynı şey olacağını

Answer 3

İşte Lasttatmin eden başka bir yasa :

forall (t :: Type) (x, y :: t).
  Last (Just x) <> Last (Just y) === Last (Just y)

Başka bir yasayı karşıladığından, özgür Monoid olmamalıdır.

Answer 4

İlk olarak, serbest monoidlerin tanımının üzerinden geçelim. Serbest bir monoidi, monoid kanunlara ve başka hiçbir şeye uymayan bir yapı olarak tanımlamanın nasıl mümkün olduğunu hiçbir zaman tam olarak anlamadım . Bir şeyin yukarıda belirtilenler dışında hiçbir kurala uymadığını nasıl kanıtlarız? Yoksa bu sadece bir sezgi mi?

Serbest monoidlerin amacını göstermeme izin verin.

Sana söylersem bir monoid bazı unsurlarla, var a, b, c, sen bundan ne çıkarabiliriz?

• Biz karıştığı ifadeleri yazarak o Monoid daha unsurları bulabilirsiniz jeneratörler a , b, cve monoid işlemleri (+)ve 0(aka. (<>)Ve mempty). (Bu cevabın ikinci yarısında bkz. Tanım 1.)
• Bazı ifadelerin aynı unsuru gösterdiğini kanıtlamak için monoid yasaları kullanabiliriz: gibi denklemleri ispatlayabiliriz ((a + 0) + b) = (a + b). Aslında (Tanım 2.), biz sadece bu bilgiyle kanıtlayabilirim denklemler herhangi değerler için herhangi Monoid hangi tutun denklemleri vardır a, b, c. (Teorem 1.)

Ya sadece monoid yasalarla kanıtlayamayacağımız denklemler? Örneğin kanıtlayamayız (a + b) = (b + a). Ama (a + b) /= (b + a)sadece monoid yasaları bilirsek, onun olumsuzluğunu da kanıtlayamayız . Bu ne anlama geliyor? Denklemin bazı monoidlerde (örneğin, değişmeli monoidlerde) geçerli olduğu, ancak diğerlerinde geçerli olmadığı ortaya çıktı: örneğin, x + y = yhemen hemen herkes için bir monoid seçin xve y(bu LastHaskell'deki monoid), eğer farklı seçersek ave bsonra (a + b) /= (b + a).

Ama bu sadece bir örnekti. Genel olarak, sadece monoid yasalarla kanıtlayamayacağımız denklemler hakkında ne söyleyebiliriz? Kesin cevap, aslında, evrensel bir counterexample ücretsiz monoid sunar: kanıtlanamayan denklemler serbest Monoid sahteysen (tarafından oluşturulan a, b, c). Diğer bir deyişle, bir denklemi e = fsadece ve ancak serbest monoidde doğruysa ("eğer" vurgusu) sadece monoid yasaları kullanarak kanıtlayabiliriz . (Teorem 2) Bu, serbest monoidin "yalnızca monoid kanunlara uyup başka hiçbir şeye uymadığı" sezgisine karşılık gelir.

Peki bu işlev, Last'i serbest bir monoid yapar mı? Daha genel olarak, Monoid (T a) için yasalara uyan bir örnek varsa, T serbest bir monoid midir?

LastO aslında monoid yasalarından tamamen kanıtlayabilirim olandan gerçek daha denklemleri yapar çünkü monoid özgür değildir. Diğer yanıta bakın :

forall (t :: Type) (x, y :: t).
  Last (Just x) <> Last (Just y) === Last (Just y)

---

İşte yukarıdakilerin nasıl resmileştirileceğinin bir taslağı.

Tanımlama 1. grubu monoidal ifadeleri (bazı atom semboller) tarafından oluşturulan A, B, Cgramer ile tanımlanır:

e ::=
  | A | B | C   -- generators
  | e + e       -- binary operation (<>)
  | 0           -- identity (mempty)

Demek ki, herhangi bir "uygun Monoid" terimi, Monoid verilen (M, (+), 0)bazı seçilmiş elemanları ile a, b, ciçinde M(ayrı olması olmayan), bir ekspresyon ebir öğesini belirtmektedir eval eiçinde M.

Tanım 2. Bir denklem ifadeleri bir çift yazılı olduğu e ~ f. Set kanıtlanabilir denklemlerin denklemlerin en küçük kümesidir ( "en küçük" içerme tarafından sipariş olduğunda) aşağıdaki karşılamasıdır:

1. Bu monoid yasalarını içermektedir: (e + 0) ~ e, (0 + e) ~ e, ((e + f) + g) ~ (e + (f + g))kanıtlanabilir bulunmaktadır.
2. Bu bir eşdeğerlik ilişkisidir (bir dizi demeti bir ilişki olarak görmek): örneğin, dönüşlülük e ~ eiçin kanıtlanabilir.
3. Bu bir eşleşme ilişkisidir: eğer e ~ fkanıtlanabilirse (g + e) ~ (g + f)ve (e + g) ~ (f + g)kanıtlanabilirse.

(Bu tanımın fikri, " e ~ fkanıtlanabilir" iddiasının ancak ve ancak bu kuralları "uygulayarak" çıkarılabilmesi durumunda geçerli olmasıdır. "En küçük küme" bunu resmileştirmek için geleneksel bir yöntemdir.)

"Kanıtlanabilir denklemler" tanımı keyfi görünebilir. Bunlar "kanıtlanabilirliği" tanımlamak için doğru kurallar mı? Neden özellikle bu üç kural? Özellikle, benzerlik kuralı böyle bir tanım vermeye yönelik ilk girişimde açık olmayabilir. Aşağıdaki teoremlerin, sağlamlığın ve bütünlüğün amacı budur. Bir (yedekli olmayan) kural eklerseniz sağlamlığı kaybederiz. Bir kuralı kaldırırsanız eksiksizliği kaybederiz.

Teorem 1. (Sağlamlık) Eğer e ~ fkanıtlanabilirse, o zaman eval e = eval fherhangi bir "uygun monoid" de M.

Teoremi 2. (Bütünlük) ise e ~ fdaha sonra anlamlara sahiplerdir farklılık, kanıtlanabilir değildir F, eval e /= eval f, burada File yaratılan serbest monoid olup A, B, C.

(Sağlamlığı kanıtlamak eksiksizlikten çok daha kolaydır. Okuyucu için alıştırmalar.)

Bu tamlık teoremi, serbest monoidin bir karakterizasyonudur: Fteoremin ifadesini doğru tutan diğer herhangi bir monoid , serbest monoide göre izomorfiktir (teknik olarak, bu hem tamlığı hem de gösterme fonksiyonunun eval : Expr -> Mkapsayıcı olduğu varsayımını gerektirir ). Bu nedenle, "listelerin monoid" yerine "serbest monoid" diyebiliriz; bu uygulama, temsilin önemli olmadığı bağlamlarda ("izomorfizme kadar") en doğrudur.

Aslında, "serbest monoid" i eşdeğerlik bağıntısı ile monoidal ifadelerin bölümü " _ ~ _kanıtlanabilir" olarak tanımlarsanız, tamlık önemsizdir . Zor çalışma aslında ayrı bir kanıta dayanıyor, bu monoidin monoid listelerin izomorfik olduğunu.