Wenn "Liste" ein Monoid ist, was ist sein "Set"?

Nur durch category theory book lesen, und beschlossen, es auf Haskell anzuwenden.Wenn "Liste" ein Monoid ist, was ist sein "Set"?

Der Autor definiert Monoid als:

Monoid ist eine Gruppe L mit einer binären Operation ausgestattet *: LxL-> L und einem aufstrebenden Einheitselement U in L, so daß etc ...

Bei einer "List" -Struktur als Monoid ist klar, dass die binäre Operation concat und die Einheit [] ist.

Aber was ist das Set M hier? Ich versuchte L = {set of all lists}, aber ich denke, dass führt mich in Schwierigkeiten mit "ist L in L?" Frage, die scheint das gleiche Problem wie Sets haben.

Oder denke ich an etwas falsch?

BEARBEITEN: Wie von @ applicative angegeben, sind Haskells Listen Monoids genannt Free monoids!

Quelle

2012-10-17 drozzy

In der Mathematik der Trick zu vermeiden" L in L "Probleme wechseln Sie von der normalen Mengenlehre (zermelo-fraenkel) zu einer Unterscheidung zwischen Mengen und Klassen und dann können Sie von der Klasse aller Sätze sprechen, oder die Klasse aller Listen. Außerdem denke ich, dass Sie sich auf das Russel-Paradox beziehen, das sich auf die {Menge aller Mengen bezieht, die * sich nicht selbst enthalten}. – epsilonhalbe

Beachten Sie, dass "die Menge aller Listen" selbst keine Liste ist, so dass es nicht sofort zu Widersprüchen kommt, die denen der naiven Mengenlehre analog sind. – Ben

Meinst du 'concat :: [[a]] -> [a]' für deine binäre Operation, oder '(++) :: [a] -> [a] -> [a]'? Es ist tatsächlich * eine Art, in der die erstere eine monoidale Operation ist, aber es ist eine ziemlich obskure ... –

Anstatt zu sagen "Liste ist ein Monoid", wäre es genauer zu sagen "Für alle Typen a ist der Typ [a] ein Monoid". Also für jeden bestimmten Typ a, wird Ihr L L = {set of all lists of as} sein. Und mit dieser Definition kann L natürlich nicht sich selbst enthalten.

Quelle

2012-10-17 04:35:30 sepp2k

Also ... wird das Set immer ein Element enthalten? Was, wenn wir zwei Listen zusammenstellen, wie wird dieser Monoid aussehen? Z.B. [a] concat [a] ... – drozzy

@drozzy Ich sprach über den Typ '[a]' (wie in "einer Liste von' a's "), nicht den Wert' [a] '(wie in" eine Liste mit einem einzelnen Element namens "a". – sepp2k

Oh, hab es! Ist das also nicht gleichbedeutend mit einer regulären ol-mathematischen Menge mit einer Vereinigungsoperation und einer leeren Menge? – drozzy

Für jede Art t Sie, dass

L = all elements of the type [t]

dann L ein Monoid in der trivialen Weise ist ++ mit haben kann. In der Tat, wir dies in Haskell formalisieren

class Monoid m where 
    mempty :: m 
    mappend :: m -> m -> m

dies ist eine „Klasse“ von Typen, die die erforderlichen Operationen haben einen Monoid zu bilden, so

instance Monoid [a] where 
    mempty = [] 
    mappend a b = a ++ b

in der Tat ist dies bekannt als die " free monoid on a "

Quelle

2012-10-17 04:47:41

Wenn Sie 'alle Elemente von [t]' sagen, meinen Sie 'L = {t1, t2, ...}' oder 'L = {{t1}, {t1, t2}, ...}'? (wobei 't1, t2..' vom Typ' t' sind) – drozzy

@drozzy: Sagen wir 't = Bool', dann' L = {[], [False], [True], [False, False], [Falsch, Wahr], [Wahr, Falsch], [Wahr, Wahr], ...} '. (Genau genommen können Sie aber auch Böden einschließen). – hammar

@hammar und '[True, True, False]' etc ... Nur klärend kann es mehr als zwei Elemente sein, solange es "endlich" ist (was eine ziemlich seltsame Definition ist, da ich potentiell mit einem kommen kann Unendliche Menge wie diese - ich denke, kann Speichergrenze auf Computern als ein begrenzendes Kriterium denken!) – drozzy

Wenn "Liste" ein Monoid ist, was ist sein "Set"?

Antwort

Verwandte Themen